考察
各boxについて必要なのは含まれるcolorの集合で、同colorのballが複数あっても出力への寄与は1である。
query後のbox bはset[a]∪set[b]、box aは空なので、物理containerを交換してから小さいsetを大きいsetへinsertしても論理結果は同じである。
重複を消すsetでは所属サイズの倍増は保証されない。例えば{1,2}と{2,3}のunionはサイズ3である。償却解析では色名でなく各container内の要素実体を数え、重複insertで消える実体にも仕事を課金する。
採用する候補: boxごとにcolor setを持ち、sizeの小さいsetを大きいsetへmergeして必要ならcontainerをswapする。
棄却する候補: 常にset[a]の全colorをset[b]へ順にinsertする。
大集合aを小集合bへ繰り返し移すquery列で、同じ多数colorを何度も処理する。
棄却する候補: 各boxにN色のboolean arrayを持ってunionする。
1 queryあたりN走査と全体N^2 memoryが必要になる。
小集合サイズs、移動先t≥s、重複数dとする。
初期box iのsetへC_iを1つ入れる。query(a,b)でsize(set[a])>size(set[b])なら2つのset handleをswapする。その後set[a]の全colorをset[b]へinsertし、set[a]をclearする。size(set[b])を出力する。
典型の発動条件
small-to-large merging
発動条件: 集合union queryが続き、片方containerを空にできるとき。
常に小集合の要素を大集合へ移す。
logical IDとphysical containerのswap
発動条件: 操作結果の格納先IDが固定だが効率的なmerge方向は逆になり得るとき。
container handleをO(1)交換して意味を合わせる。
問題固有の要素
「aからbへ移す」という向きはballの論理状態だけの指定で、set objectのidentityには意味がないため、merge前のswapで計算量を最適化できる。
別の問題へ持ち帰る視点: 可変集合問題では外部IDと内部containerをpointerで分離するとsmall-to-largeの向きを自由に選べる。
正当性
set[a]が大きいときset[a],set[b]自体をswapすれば、その後smallなaをlargeなbへmergeしても、最終的にunionがbox b、空がbox aになる。 小集合サイズs、移動先t≥s、重複数dとする。d≥s/2ならs回の処理をd個の消滅実体へ高々2ずつ課金する。d<s/2ならs-d個の生存実体へ高々2ずつ課金し、その所属サイズはt+s-d>3s/2となる。消滅への課金は一実体一回、生存への課金はサイズの単調増加によりO(log N)回なので、全insert試行はO(N log N)。平衡木setなら一試行O(log N)で全体O(N log²N+Q)。新規実体の再生成がある問題では別途その総数を界す。 queryの向きと物理merge方向をhandle交換で分離し、全insert回数をsmall-to-largeで償却できる。
実装上の注意
- swap後もloop対象が小さい論理set[a]、結果が論理box bのset[b]になる順序を守る。
- merge終了後set[a]を必ず空にし、次queryで古いcolorを残さない。
復習の核
- a側が大きいqueryでset objectをswapしてからmergeし、最終的なbox aが空・box bがunionになっているかIDを追う。
計算量と制約
時間
O(N log²N+Q)、平衡木set。重複が多い移動を消滅へ課金する償却解析。
空間
O(N+Q)。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N, Q \leq 200000; 1 \leq C_i \leq N; 1 \leq a, b \leq N; a \neq b; All input values are integers.
出典