マージテクとは？
- mapやsetやvectorなど、2つのデータをマージするときに小さい方から大きい方にマージすることでマージのオーダーが減るテクのこと
大変なルート😢
#ABC202 E通した。オイラーツアーではない悪手(?)解法。クエリ先読み&木の深さごとのカウントをmapで持って親に統合しつつクエリにも答える。統合した子はclearして捨てる。mapのマージテクのためにmapの実体を指す変換表も持つ必要があり厳しかった
— peroon_cp💧 (@peroon_cp) May 22, 2021
- この例では根側にマージしたいが根側のmapの方が小さい時に困るのでマージされた実体のindexを別に持っている
- ✅https://atcoder.jp/contests/abc202/submissions/22845981
コンテナのswapはO(1)😊
- というのがあり、これを使えば根側のmapが常に大きい側にできる
- 上記とは違う問題ではあるが、それを使うと下記のようによりシンプルに書ける
- ✅https://atcoder.jp/contests/abc183/submissions/23094643
