考察
x_i は直前の答え z により暗号化されるため全挿入値を先読みできず、通常の座標圧縮を前処理として使えない。一方、値域は [1,10^9] で挿入点は Q 個だけである。
昇順列を左区間、右区間の順に連結すると、左の要素数が奇数か偶数かだけで右区間の奇数番目・偶数番目の役割が決まる。
採用する候補: 必要な経路だけ生成する動的セグメント木に、要素数・局所奇数番目和・局所偶数番目和を持つ
左右の情報を個数の parity で結合でき、点追加後の根の奇数番目和がそのまま答えになる。ノード数と時間はいずれも Q log 10^9 である。
棄却する候補: 各追加後に配列へ挿入して全体を sort し、奇数番目を走査する
一回 O(i log i) 以上を要し Q=3×10^5 では間に合わず、前回答依存の値も事前処理できない。
左の個数が偶数なら親の odd=left.odd+right.odd、even=left.even+right.even、奇数なら右の odd/even を交換して足す。
同じ値が複数回入る葉でも、個数 c と値 x から odd=ceil(c/2)x、even=floor(c/2)x と表せるため、重複を特別な別構造で管理する必要はない。
根区間を [1,10^9+1) として x_i の根から葉までだけ生成し、葉の個数を 1 増やす。帰りがけに parity 付き結合で三つ組を更新し、root.odd を z として出力して次の x_i を計算する。
典型の発動条件
動的セグメント木
発動条件: 座標域は巨大だが、オンライン点更新で実際に触る座標数が少ないとき。
各挿入につき深さ約 30 のノードだけ生成し、未生成部分を単位元として扱う。
parity を含むモノイド
発動条件: 整列列の交互位置の集計を、連続区間の連結として求めたいとき。
区間長の偶奇に応じて後半の odd/even 集計を交換する結合則を定義する。
問題固有の要素
奇数番目和は値だけの可換な和ではないが、「個数」と偶奇別二和を組にすれば、値域順の区間連結に対して結合可能になる。
別の問題へ持ち帰る視点: 順位の偶奇が境界をまたいで反転する集計では、部分列長の parity をモノイド状態へ加える。
正当性
左右連結で右側の順位は左側の長さだけずれる。偶奇に応じた二和の交換はこのずれを正確に表すため、節点は常に局所順位の奇数和・偶数和を持つ。等しい値をまとめた葉も同じ定義を満たし、根の奇数和が整列後の答えになる。
実装上の注意
- z と区間和は 32 bit を超えるので 64 bit 整数を使い、(y_i+z) mod 10^9 の加算順にも注意する。値域右端 10^9 を含む半開区間を確認する。
復習の核
- 同値を連続挿入する場合、最小値・最大値を交互に入れる場合、z が 10^9 を大きく超える場合を multiset の全 sort と比較する。
計算量と制約
時間
O(Q log U)、U=10⁹のオンライン値域。
空間
O(Q log U)、生成済み経路node。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \le Q \le 3\times 10^5; 0 \le y_i < 10^9; 1 \le x_i \le 10^9; All input values are integers.
出典