Chef And Easy Xor Queries [CodeChef December Challenge 2017 E]

https://www.codechef.com/DEC17/problems/CHEFEXQ

長さNの配列Aがある。
以下のクエリを処理する。
クエリ1 i番目をxに更新する。
クエリ2 j≦iで[1,j]が"magical subarray"である個数を答える
magical subarray : xor和がKである

前提知識

• 平方分割

解説

このままではクエリ2が扱いにくいので、問題を言い換えておこう。
B[i]をA[0] xor A[1] xor ... xor A[i]として考えよう。
すると、2つのクエリは以下のように変わる。
クエリ1 B[i..N]へA[i] ^ xをxorし、A[i] = xにする
クエリ2 B[0..j]でKである個数を答える

平方分割でこれを解決する。
cnt[s][i] := s番目のバケットで=iである個数
lazy[s] := s番目のバケットで遅延させているxor計算
cnt配列に何が入っているかはinit関数の初期化を見れば分かるだろう。
updateもgetも一般的な平方分割。

const int S = 400;
int N, Q, A[101010];
//---------------------------------------------------------------------------------------------------
int B[101010];
int cnt[S][1 << 20];
int lazy[S];
void init() {
    rep(i, 0, N) B[i] = A[i];
    rep(i, 1, N) B[i] ^= B[i - 1];
    rep(i, 0, N) cnt[i / S][B[i]]++;
}
void update(int L, int R, int v) { // [L,R)にxor v
    int p = v;
    v = v ^ A[L];
    A[L] = p;

    while (L < R && L % S != 0) {
        cnt[L / S][B[L]]--;
        B[L] ^= v;
        cnt[L / S][B[L]]++;
        L++;
    }

    while (L < R && R % S != 0) {
        R--;
        cnt[R / S][B[R]]--;
        B[R] ^= v;
        cnt[R / S][B[R]]++;
    }

    rep(i, L / S, R / S) lazy[i] ^= v;
}
int get(int L, int R, int K) { // [L,R)で=Kの個数
    int res = 0;

    while (L < R && L % S != 0) {
        if ((B[L] ^ lazy[L / S]) == K) res++;
        L++;
    }
    while (L < R && R % S != 0) {
        R--;
        if ((B[R] ^ lazy[R / S]) == K) res++;
    }

    rep(i, L / S, R / S) res += cnt[i][lazy[i] ^ K];

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    
    init();

    rep(q, 0, Q) {
        int a, b, c; cin >> a >> b >> c;
        if (a == 1) {
            b--;
            update(b, N, c);
        } else {
            printf("%d\n", get(0, b, c));
        }
    }
}