L: XORed Array

全体FA: touhokudai (49:05)�オンサイトFA: touhokudai (49:05)

AC: 9/26

原案: zawatin, writer: amesyu

問題概要

長さNの非負正数列Aが与えられる。�Q回下記の操作を行った後のAを出力せよ。

• L, R, X が与えられる。 i = L, L + 1, … , R について�Ai = Ai xor (X + i - L) と更新する。�
• 1 ≤ N ≤ 2×10⁵
• 1 ≤ Q ≤ 5×10⁵
• 0 ≤ Ai < 2³⁰
• 1 ≤ li < ri ≤ N
• 0 ≤ xi < 2³⁰

解法

2^kの位が0か1になるのは2^k+1の周期がある。���������前半2^kは0、後半2^kが1になっている。

解法

値を +1 してみる。���������周期が左にずれた。(循環している)

解法

i = 0, 1, 2 … N の順にAiに作用する寄与を求めていく時、�各ビット毎に2^k+1の周期の配列を左に1回シフトを行う。

-> 1シフト行ったことにして1寄与する範囲をずらせばOK！

​

解法

kビット目におけるxの寄与の位置というのはxを2^k+1で割ったあまりで求めることができる。毎回寄与は1回シフトを行うのでi = Lのときに挿入するときは位置をL回左にシフトした位置になることに注意。

�1寄与している範囲に含まれている個数が奇数ならば�A[i] = A[i] xor 2^k で更新を行う。

解法

今回の制約ではxi < 2^30であるため k = 30 まで確かめる必要がある。(xi + N - 1)が最大値なのでk = 29 だと足りない(罠)��2³⁰⁺¹の配列を作るのは絶望的... ��1. 使われる範囲の個数は少ないので利用する�2. 上位ビットは別の操作で代用する

解法

kが大きい部分は1寄与する範囲が大きいので直接範囲に作用させる。N ≤ 2×10⁵ より 18 ≤ k ならば範囲は一個しかないため、imos法などを用いて範囲の最初に1、最後に1を立てておけばよい。

時間空間ともにO((N + Q)logN) で解けた。