考察
区間内で色 c が cnt_c 人なら作れる pair は floor(cnt_c/2) で、答えは色ごとのこの値の和になる。query 間で端点を一つ動かすと変化するのは追加・削除した一色だけである。
色を一個追加したとき旧個数が奇数なら pair が1増え、削除時は旧個数が偶数なら1減るため、区間状態を定数時間で更新できる。
採用する候補: query を Mo's algorithm の順に並べ、現在区間の色頻度と pair 総数を四種類の端点移動で保つ。
各 query を独立集計せず、近い区間間で O(1) update を共有でき、Q=10^6にも対応できる。
棄却する候補: 各 query で区間を走査して色頻度を作り直す。
長い区間 query が多数あると総走査量が NQ になる。
非線形な floor(cnt/2) でも、一個の増減差は cnt の偶奇だけで決まるため Mo の add/remove に必要な十分状態は頻度と総 pair 数だけである。
query を左端 block と右端で Mo 順に sort する。現在 [L,R] を伸縮し、add(x) は count[A_x] が奇数なら ans++、remove(x) は削除前 count[A_x] が偶数なら ans-- として頻度を更新し、元 query index へ ans を保存する。
典型の発動条件
Mo's algorithm
発動条件: 静的配列の多数の offline range query で、要素一個の追加・削除から答えを更新できるとき。
端点移動総数が小さくなる block 順へ query を並べ替える。
頻度関数の差分更新
発動条件: 答えが Σg(cnt_c) の形で、cnt を±1した差が簡単なとき。
対象色の g(new)-g(old) だけを総和へ反映する。
問題固有の要素
pair 数の増減条件が追加前は奇数、削除前は偶数と逆になる。
別の問題へ持ち帰る視点: floor や parity を含む頻度集計では add/remove の差を別々に式で導き、対称だと決めつけない。
正当性
一色で作れる組数は、その人数を二人ずつ分けた最大数である。他色との組は作れないため色別に足せばよい。端点移動時に変わる一色の差分を反映することで、現在区間の最大組数を常に保つ。
実装上の注意
- remove 判定は count を減らす前の偶奇で行う。Q が10^6なので query object、sort comparator、入出力の定数倍を抑え、右端順を block ごとに反転する実装も検討する。
復習の核
- 同じ色の個数を0→1→2→1→0と動かし、pair 数の差と add/remove の判定時点を表にして覚える。
計算量と制約
時間
O(Q log Q+QB+N²/B)、Bは左端block幅。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)、頻度とquery。
制約との対応
公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: All values in input are integers.; 1 \le N \le 10^5; 1 \le Q \le 10^6; 1 \le A_i \le N; 1 \le l \le r \le N in each query.
出典