考察
区間に値xを一個追加すると同値三つ組はC(cnt_x,2)個増え、削除時も逆順で定数時間更新できる。
採用する候補: Mo's algorithmで区間端を並べ替える
全質問が事前にあり、左右端一歩の追加削除がO(1)なので総移動量を約N√Qへ抑えられる。
棄却する候補: 各質問で頻度を数え直す
区間長の総和がO(NQ)になり得る。
答えΣ_x C(cnt_x,3)を直接持てば、追加前cntのC(cnt,2)を足し、削除後のcntに対する同値を引くだけでよい。
質問を左端blockと右端順でソートし、現在区間を伸縮しながらfreq[A_i]と三つ組数を差分更新して元の質問順へ答える。
典型の発動条件
Mo's algorithm
発動条件: 静的配列の多数区間質問で端点一歩更新が軽い。
質問順をblock分割で並べ替えて区間移動を共有する。
組合せ数の差分
発動条件: 頻度cに一要素を加えた統計量C(c,3)の変化を知りたい。
C(c+1,3)-C(c,3)=C(c,2)を使う。
問題固有の要素
三重ループをせず、値別頻度の三項組合せ和をオンライン維持できる。
別の問題へ持ち帰る視点: 区間内k組数は追加時に既存(k-1)組数を足す。
正当性
同じ値の三位置は、頻度から三つ選ぶ組合せに一致する。一要素の追加で新たにできる三つ組は既存の二位置との組だけであり、削除はその逆である。この差分を足し引きするので、Mo順によらず現在区間の答えを保つ。
実装上の注意
- 追加と削除のfreq更新順を逆にし、答えは64ビットで保持する。
復習の核
- 素朴三重ループと照合し、全同値・全相異・長さ3未満・同じ区間の重複質問を確認する。
計算量と制約
時間
O(Q log Q+QB+N²/B)、B≈N/√Qで移動O(N√Q+Q)。 左端block幅Bでは左端の移動がO(QB)、右端は高々N/B個のblockで各O(N)なのでO(N²/B)。B=max(1,⌊N/√Q⌋)で均衡させる。
空間
O(N+Q)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 1 \leq Q \leq 2 \times 10^5; 1 \leq A_i \leq 2 \times 10^5; 1 \leq l_q \leq r_q \leq N; All values in the input are integers.
出典