考察
各位置の集合への区間追加・削除は f(X)=(X\a)∪b という写像で合成できる。一方、区間最大要素数とその個数だけでは、対象要素が各集合に入っているか分からず写像を常に適用できない。
採用する候補: 和集合 O・共通部分 A・最大サイズ M・達成数 C を持つ Segment Tree Beats を構築し、一括適用不能な節点だけ子へ降りる。
失敗するたび曖昧要素 O\A が減り、その増加総量も制限されるため全クエリを償却高速に処理できる。
棄却する候補: 通常の遅延セグメント木に最大サイズと達成数だけを持たせる。
追加・削除対象が区間内の集合に混在すると各葉のサイズ変化が異なり、節点情報だけから mapping を計算できない。
(O\A)∩(a∪b)=∅ なら、操作対象の各要素は区間内の全集合に含まれるか全く含まれないので、全葉のサイズ変化が同じで節点へ一括適用できる。
mapping 失敗で子へ降り再集約すると O\A のサイズが真に減る。クエリ一回で曖昧度を増やせる節点は O(log N)、増分は高々 1 である。
集合を 64-bit mask とし、各節点に OR、AND、最大 popcount、最大達成葉数、遅延写像 (remove,add) を保持する。完全被覆時に成功条件を満たせば写像と集約を更新し、失敗なら push して子へ再帰する。根の M,C を各質問後に取得する。
写像を正準形f(X)=(X&~a)|b、a&b=0で持つ。先に(a1,b1)、後に(a2,b2)を適用した合成は、b=(b1&~a2)|b2、a=(a1|a2)&~b。後の追加が先の削除を上書きする順序を保つ。
一括適用時はORとANDをともにfで更新する。全葉共通のサイズ変化はΔ=popcount(b&~O)−popcount(a&A)なので、最大サイズM←M+Δ、達成数Cは不変。初期の全空集合の節点ではO=A=M=0、Cは実際の葉数とする。
ポテンシャルを全内部節点のpopcount(O&~A)の和に取る。完全被覆で失敗した節点では、混在していた対象bitが操作後に全て0または全て1となり、一つ以上消える。曖昧度が増える可能性があるのは区間境界をまたぐO(log N)節点だけ。単bitの追加・削除一回につき各節点の増加は高々1なので、失敗下降の総数はO(NB+Q log N)。各操作の境界走査を含めO(NB+Q log N)であり、元のO((N+Q)B log N)も保守的上界として成立する。複数bitをまとめた一般写像を一回と数えるなら増加上界にBを掛ける。
典型の発動条件
Segment Tree Beats
発動条件: 区間写像を節点情報だけで適用できる場合とできない場合があり、失敗回数を単調量で償却できるとき。
集合の混在度 O\A を失敗時に減るポテンシャルとして、必要な場合だけ子へ降りる。
bitset による集合写像
発動条件: 要素 universe が機械語幅程度で、和・積・差を頻繁に扱うとき。
集合と追加・削除写像を bit mask にし、OR/AND/AND-NOT を定数時間で行う。
区間最大値と達成数の集約
発動条件: 葉の値の最大と、その最大を取る位置数を繰り返し問うとき。
子の最大を比較し、等しければ達成数を足すモノイドとして保持する。
問題固有の要素
遅延写像が適用可能かを、区間内で membership が混在する要素集合 O\A との交差だけで判定できる。
別の問題へ持ち帰る視点: Segment Tree Beats では失敗を許す代わりに、失敗のたび減るポテンシャルと更新で増える総量を明示する。
正当性
一括適用の成功条件では、操作対象bitの有無が全葉で揃っているため、全サイズが同じ量だけ変わる。混在する場合は子へ降りて同じ操作を行い再集約するので、根の最大値と達成数を常に保つ。失敗時の曖昧度減少と境界だけでの増加は、考察のポテンシャル評価が与える。
実装上の注意
- 写像合成では先の remove/add と後の操作順を保つ。葉・内部節点の OR/AND 初期値、成功時の M の増減と C 不変を整合させる。
復習の核
- 一括適用条件が対象 bit の membership 一様性と同値か、mapping 失敗時にポテンシャルが減ることを確認する。
計算量と制約
時間
償却O((N+Q)B log N)、Bは集合のbit数(64-bit mask内)。曖昧bitの減少へ失敗下降を課金する。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 3\times 10^5; 1\leq Q \leq 3\times 10^5; For each query, 1 \leq L \leq R \leq N.; For type 1,2 queries, 1 \leq x \leq 60.; All input values are integers.
出典