题解：P11872 [威海市赛 2024] 异或盒子 1

· · 题解

有一个长度为 n 的序列 a，有以下 3 种操作：

  • 将一个 a_x 修改为 y。
  • 全局 +1。
  • 询问全局异或和。

思路

考虑 01 Trie。

但是，如果和普通 01 Trie 一样，从高位往低位建树，一次会修改很多节点，并且这题不需要查询前缀，于是反过来，考虑从低位往高位建树。

考虑维护一个 s_u 表示 u 子树内的异或和。但是，我们发现，这样对于边为 1 的子节点，不好直接更新异或和，由于当子树内数字数量（叶子数量）为偶数时，这一位会抵消，于是我们多维护一个字数内数字数量。

考虑全局 +1，会导致 1 进位变成 0，0 变成 1，于是交换左右子树，往 1 方向递归，并且打上全局标记。

插入和正常 01 Trie 一样。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int MAXM = 4e7 + 10;
const int MAXH = 30;
int n, m, a[MAXN];
vector <int> G[MAXN];
int ch[MAXM][2], w[MAXM], xor_sum[MAXM], cnt, lzy;
//ch[u][0/1] 表示 0/1 方向儿子，lzy 是全局标记
int root;
int fa[MAXN];
void pushup(int u) {
    //w 奇偶性，xor_sum 就是子树异或和 
    w[u] = xor_sum[u] = 0;
    if (ch[u][0]) {
        w[u] ^= w[ch[u][0]];
        xor_sum[u] ^= (xor_sum[ch[u][0]] << 1);
    }
    if (ch[u][1]) {
        w[u] ^= w[ch[u][1]];
        //偶数的话这一位就抵消了 
        xor_sum[u] ^= (xor_sum[ch[u][1]] << 1) | (w[ch[u][1]] & 1);
    }
} 
void add(int u) {
    swap(ch[u][0], ch[u][1]);
    if (ch[u][0]) add(ch[u][0]);
    pushup(u);
}
void insert(int &u, int x, int dep) {
    if (!u) u = ++cnt;
    if (dep > MAXH) {
        //写 ^ 1 可以让两次插入抵消变成删除，就不用再写删除了 
        w[u] ^= 1;
        return;
    }
    insert(ch[u][x & 1], x >> 1, dep + 1);
    pushup(u);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i], insert(root, a[i], 0);
    while (m--) {
        int op, x, y;
        cin >> op;
        if (op == 0) {
            cin >> x >> y;
            insert(root, a[x] + lzy, 0);
            //y - lzy + lzy = y
            a[x] = y - lzy;
            insert(root, a[x] + lzy, 0);
        } else if (op == 1) lzy++, add(root);
        else cout << xor_sum[root] << '\n';
    }
    return 0;
}