点击查看代码
#include <bits/stdc++.h>
using namespace std;const int N = 600005;
const int MAX_NODES = N * 25;
//max_id,存经过某个节点的最大下标，用于下界区间的判断
int ch[MAX_NODES][2], max_id[MAX_NODES];
int root[N], s[N];//s[]数组就是前缀异或数组，就是异或的前缀和，我们要求的就是val*一段区间的s[k]的最大值
int tot = 0;// id: 当前插入的原数组下标，用于判断max_id
// val: 本次要插入的值
void insert(int id, int pre, int now, int val) {max_id[now] = id; // 给当前版本盖上时间戳，下界判断int p = now, q = pre;for (int i = 23; i >= 0; i--) {int c = (val >> i) & 1;// 无脑复制旧节点的左右儿子ch[p][0] = ch[q][0];ch[p][1] = ch[q][1];// 只有新数字走的那条路，需要裂变出新节点ch[p][c] = ++tot;// 指针往下走p = ch[p][c];q = ch[q][c];// 给沿途的新节点盖上最新的时间戳max_id[p] = id; }
}//在版本R的树中，寻找下界大于等于L的最大匹配
int query(int L, int R, int val) {int p = root[R]; // 控制上界Rint ans = 0;for (int i = 23; i >= 0; i--) {int c = (val >> i) & 1;//经典求异或和套路，优先走相反分支，这里加了最大数字下标>=L的判断if (max_id[ch[p][1 - c]] >= L) {ans |= (1 << i);p = ch[p][1 - c];} else {p = ch[p][c]; }}return ans;
}int main() {ios::sync_with_stdio(0); cin.tie(0);int n, m;cin>>n>>m;//空集初始化s[0] = 0;max_id[0] = -1; // 让所有不存在的空节点的max_id都为－1，这样下界判断永远为假root[0] = ++tot;insert(0, 0, root[0], 0);// 读入初始的 n 个数字，cur_n标记当前有多少数字,表示当前的历史版本推进到哪为了max_id的处理int cur_n = n;for (int i = 1; i <= n; i++) {int x; cin >> x;s[i] = s[i - 1] ^ x;//给每一次插入都给出一个根节点，方便版本控制root[i] = ++tot;//时间戳，旧大门，新大门，当前值insert(i, root[i - 1], root[i], s[i]);}// 查询和动态增加while (m--) {char op; cin >> op;if (op == 'A') {int x; cin >> x;cur_n++;s[cur_n] = s[cur_n - 1] ^ x;root[cur_n] = ++tot;insert(cur_n, root[cur_n - 1], root[cur_n], s[cur_n]);} else {int l, r, x;cin >> l >> r >> x;//根据公式查询int val = s[cur_n] ^ x;cout << query(l - 1, r - 1, val) << "\n";}}return 0;
}
