题目大意：有一串初始长度为$n$的序列$a$，有两种操作：
- $A\;x：$在序列末尾加一个数$x$
- $Q\;l\;r\;x：$找一个位置$p$，满足$l\leqslant p\leqslant r$，使得： $a_p\oplus a_{p+1}\oplus\dots\oplus a_n\oplus x$最大，输出最大是多少。
题解：把序列前缀和，变成$S$，就变成了在$[l-2,r-1]$区间内找一个数$S_p$，使得$S_p\oplus S_n\oplus x$最大。可持久化$trie$
卡点：无
C++ Code：
#include#include #define M 24#define maxn 600010 #define N (maxn * (M + 1))int n, m;int __root__[maxn], *root = __root__ + 1, idx;int nxt[N][2], V[N], sum;void insert(int &rt, int x, int dep) { nxt[++idx][0] = nxt[rt][0], nxt[idx][1] = nxt[rt][1], V[idx] = V[rt] + 1, rt = idx; if (!~dep) return ; int tmp = x >> dep & 1; insert(nxt[rt][tmp], x, dep - 1);}int query(int x, int L, int R) { int res = 0; for (int i = M; ~i; i--) { int tmp = x >> i & 1; if (V[nxt[R][!tmp]] - V[nxt[L][!tmp]]) L = nxt[L][!tmp], R = nxt[R][!tmp], res |= 1 << i; else L = nxt[L][tmp], R = nxt[R][tmp]; } return res;}int main() { std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0); std::cin >> n >> m; insert(root[0], 0, M); for (int i = 1, x; i <= n; i++) { std::cin >> x; insert(root[i] = root[i - 1], sum ^= x, M); } while (m --> 0) { char op; int l, r, x; std::cin >> op >> l; if (op == 'A') { root[n + 1] = root[n]; insert(root[++n], sum ^= l, M); } else { std::cin >> r >> x; std::cout << query(x ^ sum, root[l - 2], root[r - 1]) << '\n'; } } return 0;}