はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるマージテク問題まとめ

マージテク

  • 正式名称、データ構造をマージする一般的なテク
  • 集合をまとめる時に大きい方に小さい方を移動させることでマージさせると計算量がならしO(logN)
  • 発祥の地
  • 併合(マージ)可能なheapをmeldable heapといい、実装の1つとしてマージテクを使うものがある(O(log^2N),Skew HeapだとO(logN))
  • 複数配列を全部FFTで畳み込む時にマージテクっぽい技を使うときがある こっちに書いた

問題

木DPっぽいやつをマージテクで高速化

  • CSAcademy Uniform Trees
  • ECR2 Lomsat gelral 解説1 解説2 解説3
  • ARC086 Smuggling Marbles (木のマージテクだけどO(N)になる)
  • CF221 Tree and Queries 解説1 解説2
    • ある色の頂点数がx以上の色の数を数えるdpのマージが、一見、マージテクになっていないように見えるが、ある色に対してマージ元にi個、マージ先にj個あった場合に[i+1,i+j]に+1をしていくのだが、この個数を全て足すとマージ先の頂点数と等しくなる
    • その為、マージ先の頂点数を別途数えて、その数を見てマージテクをやろう

【発展的話題】Sack (dsu on tree)