[NowCoder11254I]Kuriyama Mirai and Exclusive Or

考虑异或差分 $s_i=a_i\oplus a_{i-1}$ 。操作 1 直接 $s_l\oplus x,\ s_{r+1}\oplus x$ 即可。考虑操作 2 ，设 ${\rm lowbit}(x)=2^k$ ，则对于 $i-l<2^k,\ \ a\oplus(x+i-l)=a\oplus(x|(i-l))=a\oplus x\oplus (i-l)$ ，相当于对于区间 $[l,\ l+2^k)$ ，区间异或 $x$ 后再依次异或上 $0,\ 1,\ 2,\ ...,\ 2^k-1$ ，第一部分与操作 1 同理，第二部分可以直接先打个标记，记为 $b_{i,k}$ ，执行完后 $x\gets x+2^k,\ \ l\gets l+2^k$ 。重复上述操作直到 $l+2^k-1>r$ ，此时再从大到小枚举 $k$ 执行上述操作直到填满区间 $[l,\ r]$ 即可。处理完所有操作后考虑处理 $b_{i,k}$ ，从大到小枚举 $k$ ，实际上 $b_{i,k}$ 相当于 $0,\ 1,\ 2,\ ...,\ 2^{k-1}-1,\ 2^{k-1}|0,\ 2^{k-1}|1,\ ...,\ 2^{k-1}|(2^{k-1}-1)$ ，相当于标记 $b_{i,k-1}$ 和 $b_{i+2^{k-1},\ k-1}$ ，然后区间 $[i+2^{k-1},i+2^k)$ 异或上 $2^{k-1}$ ，注意判断是否越界。 $O((n+q)\log n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 5;
int n, q, pw[20], s[N];
bitset<20> b[N];
inline void Solve() {
    int x, y = 0;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &x), s[i] = x ^ y, y = x;
    for (int op, l, r; q--;) {
        scanf("%d%d%d%d", &op, &l, &r, &x);
        if (!op) {
            s[l] ^= x, s[r + 1] ^= x;
            continue;
        }
        for (int i = 0; i <= 19; ++i)
            if (x & pw[i] && l + pw[i] - 1 <= r)
                b[l][i].flip(), s[l] ^= x, s[l += pw[i]] ^= x, x += pw[i];
        for (int i = 19; i >= 0; --i)
            if (l + pw[i] - 1 <= r)
                b[l][i].flip(), s[l] ^= x, s[l += pw[i]] ^= x, x += pw[i];
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 19; j >= 1; --j)
            if (b[i][j]) {
                b[i][j - 1].flip();
                if ((x = i + pw[j - 1]) > n)
                    continue;
                b[x][j - 1].flip(), s[x] ^= pw[j - 1];
                if (i + pw[j] <= n)
                    s[i + pw[j]] ^= pw[j - 1];
            }
    for (int i = 1; i <= n; ++i)
        printf("%d%c", s[i] ^= s[i - 1], " \n"[i == n]);
}
int main() {
    pw[0] = 1;
    for (int i = 1; i <= 19; ++i)
        pw[i] = pw[i - 1] << 1;
    while (~scanf("%d%d", &n, &q))
        Solve();
    return 0;
}