ABC470 C - Inc, Dec, Xor

考え方

まず、実際に $A$ を用意したとして、愚直解を考えてみる。
クエリ $1$ は、その値を $1$ 増やして、全体の XOR を計算する。
クエリ $2$ は、$A$ 全体を見て、正のものは $1$ ずつ減らして、全体の XOR を計算する。
これで、 $O(NQ)$ でよければ答えが出る。
しかし、今回の制約ではこれは間に合わない。

間に合っていない部分は $2$ つ。
これらをうまく高速化してやることを考える。

まず $1$ つめは、毎回全部の XOR を取っている点。
これは、差分更新を考えることで高速化できる。
つまり、最初に全体の XOR を $1$ 度だけ計算し、その後は変化分だけ反映する。
具体的には、$A_i$ が $1$ 増減する場合、増減前の $A_i$ と増減後の $A_i$ をそれぞれ追加で XOR すればいい。

そして $2$ つめは、クエリ $2$ のときに正のものを全体探している点。
これは、実際にはかなりの部分が $0$ であることが大きな無駄となっている。
ということは、どこか別のデータに「今正の値になってる位置一覧」を用意すればよい。
減少させる回数が増加させる回数を超えることはないので、延べ回数で最大 $Q$ 回で減少処理を行える。

今正の値になってる位置一覧に set を利用した場合、計算量は $O(N+Q\log N)$ である。

入力例1での動作

入力を受け取る。
配列 a をすべて 0、XOR の値 result を $0$、正の値の位置の集合 st を空集合で初期化する。

n: 2
q: 5
a: {0, 0}
result: 0
st: {}

$1$ 個目のクエリは 1 2 である。
a[1] を 0 から 1 に増やし、st に 1 を追加する。
変更前後の値を XOR して result を更新する。

a: {0, 1}
result: 1
st: {1}

$2$ 個目のクエリも 1 2 である。
a[1] を 1 から 2 に増やす。
変更前後の値を XOR して result を更新する。

a: {0, 2}
result: 2
st: {1}

$3$ 個目のクエリは 1 1 である。
a[0] を 0 から 1 に増やし、st に 0 を追加する。
変更前後の値を XOR して result を更新する。

a: {1, 2}
result: 3
st: {0, 1}

$4$ 個目のクエリは 2 である。
st に入っている位置の値をそれぞれ $1$ 減らす。
a[0] は 0 になるので、走査後に st から削除する。
変更前後の値を XOR して result を更新する。

a: {0, 1}
result: 1
st: {1}

$5$ 個目のクエリも 2 である。
a[1] を 1 から 0 に減らし、走査後に st から削除する。
変更前後の値を XOR して result を更新する。

a: {0, 0}
result: 0
st: {}

各クエリの直後に result を出力するので、出力は次のようになる。

1
2
3
1
0

注意点

set の値を走査しながら $0$ になったら消す処理の書き方に注意。
範囲 for 文は、走っている最中にデータサイズを変えると壊れる。
よって、削除したいものを別管理しておき、範囲 for 文が終わってから削除を実行する必要がある。

別解

特になし。