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 の解説