题解 | #Kuriyama Mirai and Exclusive Or#

I - Kuriyama Mirai and Exclusive Or

题意：
序列上两种操作，对异或上，对异或上，问最后序列的样子。

思路：
区间修改，只问最后长啥样，试试看异或差分。操作直接搞就行，操作显得很复杂，看起来只能单点修改。观察这个式子。当时，这个式子等价于，也等价于，看看能否把这个异或的式子加入到异或差分中。那么首先对于这个区间，我们先对其整体异或上，然后问题就转换成了对这个区间异或上。首先肯定不能一个个推过去，这样和前面暴力是没有区别的。设，把异或的值都拿出来，得到。我们以为中间的边界，可以把右边的值写成。相当于从原本要异或的值中取出前一半，复制一份给后一半，同时将后一半的区间整体异或上。对于每个来说，我都能递归到，所以第二步就转换成了对区间的异或修改。这里每一次都递归会显得很多余，我们可以先打个标记，最后从大到小一起转移就行。

每一步完成这样的操作后，注意更新和，把他们都加上。最后一步可能会超出我需要修改的右区间，这里我们只需要从大到小枚举，尝试用去更新就行了。因为更新不了，后面填上去的数字在的二进制位上一定在最后一位后面，即一定为，所以也能转换成异或操作。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 6e5 + 7;

bool tag[N][30];
int a[N];

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i) a[i] ^= a[i - 1];
    }
    while (q--) {
        int op, l, r, x;
        cin >> op >> l >> r >> x;
        l--, r--;
        if (!op) {
            a[l] ^= x;
            a[r + 1] ^= x;
            continue;
        }
        for (int i = x & -x; l + i <= r + 1; x += i, l += i, i = x & -x) {
            a[l] ^= x;
            a[l + i] ^= x;
            tag[l][__lg(i)] ^= true;
        }
        for (int i = 29; i >= 0; --i) {
            int k = 1 << i;
            if (l + k <= r + 1) {
                a[l] ^= x;
                a[l + k] ^= x;
                tag[l][i] ^= true;
                l += k;
                x += k;
            }
        }
    }
    for (int j = 29; j >= 1; --j) {
        for (int i = 0; i < n; ++i) {
            if (!tag[i][j]) continue;
            tag[i][j - 1] ^= true;
            int k = 1 << (j - 1);
            if (i + k <= n + 1) {
                tag[i + k][j - 1] ^= true;
                a[i + k] ^= k;
            }
            if (i + k * 2 <= n + 1) a[i + k * 2] ^= k;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i) a[i] ^= a[i - 1];
        cout << a[i] << ' ';
    }
}

int main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cout << fixed << setprecision(20);
#endif
    int t = 1;
    while (t--) solve();
    return 0;
}