ABC470 C - Inc, Dec, Xor
増減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での動作
入力を受け取る。
n: 2
q: 5
1 2
1 2
1 1
2
2最初は $A=(0,0)$、全体の XOR は $0$ である。
正の値が入っている位置もまだない。
$1$ 個目のクエリは 1 2 で、$A_1$ を $1$ 増やす。
変更前の $A_1=0$ を XOR で取り除き、$A_1$ を $1$ にした後、新しい値 $1$ を XOR する。
したがって、全体の XOR は $0\mathbin{\mathrm{xor}}0\mathbin{\mathrm{xor}}1=1$ となる。
また、$A_1$ が $0$ から正の値になったので、位置 $1$ を正の値の位置一覧に追加する。
a: {0, 1}
正の値の位置: {1}
XOR: 1$2$ 個目のクエリも 1 2 で、今度は $A_1$ を $1$ から $2$ にする。
変更前の値 $1$ を XOR で取り除き、新しい値 $2$ を XOR する。
全体の XOR は $1\mathbin{\mathrm{xor}}1\mathbin{\mathrm{xor}}2=2$ となる。
a: {0, 2}
正の値の位置: {1}
XOR: 2$3$ 個目のクエリは 1 1 で、$A_0$ を $0$ から $1$ にする。
全体の XOR は $2\mathbin{\mathrm{xor}}0\mathbin{\mathrm{xor}}1=3$ となる。
$A_0$ も正の値になったので、位置 $0$ を一覧に追加する。
a: {1, 2}
正の値の位置: {0, 1}
XOR: 3$4$ 個目のクエリは 2 である。
正の値が入っている位置 $0,1$ だけを順に $1$ 減らす。
位置 $0$ では $A_0$ が $1$ から $0$ になる。
変更前後の値を XOR すると、全体の XOR は $3\mathbin{\mathrm{xor}}1\mathbin{\mathrm{xor}}0=2$ となる。
$A_0$ は $0$ になったので、処理後に正の値の位置一覧から削除する。
続いて位置 $1$ では $A_1$ が $2$ から $1$ になる。
全体の XOR は $2\mathbin{\mathrm{xor}}2\mathbin{\mathrm{xor}}1=1$ となる。
a: {0, 1}
正の値の位置: {1}
XOR: 1$5$ 個目のクエリも 2 である。
正の値が入っているのは位置 $1$ だけなので、$A_1$ を $1$ から $0$ にする。
全体の XOR は $1\mathbin{\mathrm{xor}}1\mathbin{\mathrm{xor}}0=0$ となる。
位置 $1$ も正の値の位置一覧から削除される。
a: {0, 0}
正の値の位置: {}
XOR: 0したがって、各クエリ後の答えは順に $1,2,3,1,0$ となる。
注意点
set の値を走査しながら $0$ になったら消す処理の書き方に注意。
範囲 for 文は、走っている最中にデータサイズを変えると壊れる。
よって、削除したいものを別管理しておき、範囲 for 文が終わってから削除を実行する必要がある。
別解
特になし。