Rust でのマージテク

• マージテクの例: ABC 329 F - Colored Ball

      fn solve2(&self) -> Answer {
          let Problem { n_box, nq, colors, queries } = self;
  
          // box_to_colors[box_i]: box_i 番目の箱に入っているの色の集合
          let mut box_to_colors = colors.iter().copied().map(|c| HashSet::from([c])).collect_vec();
          let mut ans = Vec::new();
          for q in queries {
              // 箱a のボールを箱 b に移す
  
              if box_to_colors[q.a].len() > box_to_colors[q.b].len() {
                  box_to_colors.swap(q.a, q.b)
              }
              for x in std::mem::take(&mut box_to_colors[q.a]) {
                  box_to_colors[q.b].insert(x);
              }
  
              ans.push(box_to_colors[q.b].len());
          }
  
          Answer { ans }
      }
  

take を使わないと shared XOR mutable で引っかかる

    fn solve3(&self) -> Answer {
        let Problem { n_box, nq, colors, queries } = self;

        // box_to_colors[box_i]: box_i 番目の箱に入っているの色の集合
        let mut box_to_colors = colors.iter().copied().map(|c| HashSet::from([c])).collect_vec();
        let mut ans = Vec::new();
        for q in queries {
            // 箱a のボールを箱 b に移す

            if box_to_colors[q.a].len() > box_to_colors[q.b].len() {
                box_to_colors.swap(q.a, q.b)
            }
            for &x in &box_to_colors[q.a] { // ここで take しないと
                box_to_colors[q.b].insert(x); // ここでエラーになる!!!
            }

            ans.push(box_to_colors[q.b].len());
        }

        Answer { ans }
    }

cannot borrow box_to_colors as mutable because it is also borrowed as immutable

std::mem

std::mem

マージテクが O(n log n)な理由

• 玉がn個あるとする。それぞれの玉の気持ちになる。玉が移動するとき、同じ袋にいる玉の数は2倍以上になる。つまり、各玉は高々 log n 回くらいしか移動しない。すべてのに対して考えることで移動回数は O(n log n ) であることがわかる
  • ABC 329 F - Colorfull Ball の解説