マージテク
- 正式名称、データ構造をマージする一般的なテク
- 集合をまとめる時に大きい方に小さい方を移動させることでマージさせると計算量がならしO(logN)
- 発祥の地
- 併合(マージ)可能なheapをmeldable heapといい、実装の1つとしてマージテクを使うものがある(O(log^2N),Skew HeapだとO(logN))
- 複数配列を全部FFTで畳み込む時にマージテクっぽい技を使うときがある こっちに書いた
問題
- Codeforces Round #396 (Div. 2) D. Mahmoud and a Dictionary
- AGC014 E. Blue and Red Tree
- HE Shubham and Tree-1
- AC Propagating Edges 解説
木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)
- CFの本家の解説
- 本質的にはマージテクと同じなのだが、定数倍軽いらしい
- 日本語解説
- 問題
- CF383 Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths 解説
- CodeChef Company and Club Hierarchies 解説
