問題概要
$N$ 人の人がいて，人 $i$ はクラス $C_i$ に属している．以下の 2 種のクエリを処理せよ．
- クエリ 1 : 人 $a, b$ が含まれる集団が合流する
- クエリ 2 : 人 $x$ が属している集団で，クラス $y$ に属している人の人数を出力する
制約
- $1 \leq N, Q \leq w \times 10^5$
- その他題意と整合性のあるいい感じの制約
Weighted-Union Heuristic
はじめに
界隈で「データ構造をマージする一般的*1なテク」と呼ばれている技法があります．``Introduction to Algorithms'' [1] では Data Structure for Disjoint Sets の章で ``Weighted-Union Heuristic'' として挙げられています． hatena diary の終了に伴い，オリジナルと言えそうな記事が消失してしまったので，二番煎じの二番煎じ*2ながら知っている範囲で書き残しておこうと思います．
データ構造をマージしたい
$n$ 個のデータ構造があり，それを順にマージしたいとします．例えばデータ構造が配列（というか std::vector）であれば，
- 片方の要素を他方へ全て追加
- 移動元のクリア
がマージの例になります（クリアはしなくてもマージできてますが，メモリを圧迫して死にたくないのでセットにしておきます）．これをデータ構造が $1$ 個になるまで行うときの計算量について考えます．
愚直に処理する場合
何も考えずにマージ処理を行っていくとどうなるでしょうか．意地悪なマージ順序を考えてあげると，最長な配列を最短な配列へマージする操作を繰り返すことで，$i$ 回目の操作では $i$ 個の要素が移動することになり，全体の計算量が $\Omega( n^2 )$ となることが分かります．
この計算量は，ちょっとした工夫で減らす事ができます．
Weighted-Union Heuristic
Weighted-Union heuristic はデータ構造のマージ時に常にサイズの大きくない方から小さくない方へマージするようにすることで全体の計算量を $O( n \log n T( n )$ にする技法です．ここで $T( n )$ は 1 つのデータの移動にかかる時間です．
この技法の計算量解析をするにあたっては，視点をちょっと変えてあげることがキモになります．配列に含まれているある要素に着目します．この要素がマージに巻き込まれたとき，マージ時のサイズの取り決めから，それが含まれるデータ構造のサイズは必ず 2 倍以上になります．全体のデータ数が $n$ であることから，ある一つの要素がマージに巻き込まれる回数は $O( \log n )$ 回であることがわかります．よって，すべての要素で考えれば，要素の移動は $O( n \log n )$ 回しか起こりません．全体の計算量はデータの移動回数と移動にかかるコストの積なので，$O( n \log n T( n )$ だと分かりました．
一般性について
この技法は，データの取り出しと挿入がサポートされているデータ構造なら何にでも適用することができ，一般性があります．
おわりに
何番煎じか分かりませんが，Weighted-Union Heuristic の解説でした．遭遇したときに毎回説明を書きたくないので，一つの記事にしておこうという感じのアレです．
参考文献
[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.
AtCoder Beginner Contest 183, E : Queen on Grid
問題概要
高さ $H$ ，幅 $W$ のグリッド状の盤面を考える．セル $( i, j )$ は空白か壁かのいずれかである．
この盤面の位置 $( 1, 1 )$ に駒が置かれている．駒は，右，右下，下のいずれかの方向に，壁にぶつからない限りにおいて何マスでも移動できる（移動方向が制限された，チェスのクイーン）．この駒を $( 1, 1 )$ から $( H, W )$ へ移動させる方法の総数はいくらか？
制約
- $1 \leq H, W \leq 2{,}000$
AtCoder Beginner Contest 183, D : Water Heater
問題概要
給湯器がひとつあり，毎分 $W$ リットルのお湯を出せる．
給湯器を使いたい人が $N$ 人いて，$i$ 番目の人は時刻 $S_i$ から $T_i$ まで（$T_i$ 丁度は含まない），$P_i$ リットルのお湯を使いたい．お湯は即座に冷めるので溜めておくことはできない．
全ての人が使いたい量のお湯を使うことはできるか？
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq S_i < T_i \leq 2 \times 10^5$
- $1 \leq W, P_i \leq 10^9$
AtCoder Beginner Contest 183, C : Travel
問題概要
$N$ 個の街があり，街 $i$ から街 $j$ へ移動するのにかかる時間は $T_{i,j}$ である．
街 $1$ を出発して，街 $1$ 以外のすべての街を丁度一度ずつ訪問してから街 $1$ に戻ってくるルートであって，所要時間が丁度 $K$ になるものは何通りあるか？
制約
- $2 \leq N \leq 8$
- $1 \leq T_{i,j} \leq 10^8$
- $1 \leq K \leq 10^9$
