ABC 293 G — Triple Index

考察

区間に値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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Triple Index の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Moの順序で区間問い合わせの差分を更新する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: Mo's algorithmによるオフライン区間問い合わせ

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: Moの順序で区間問い合わせの差分を更新する

      • 区間問い合わせの順序と追加・削除操作を設計し、端点移動の総量を評価できる。

      この解説で扱わないこと:

      • オンラインのpriority queue・multiset、および単調stack・queue。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題