题面
题解
显然，如果让你查询整个数列的最大异或和，建一颗$01Trie$，每给定一个$p$，按照二进制后反方向跳就行了（比如当前二进制位为$1$，则往$0$跳，反之亦反）。
但是现在要支持在最末尾插入和区间查询，将这颗$Trie$可持久化一下就好了（可持久化$Trie$敲板）
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::sort; using std::swap;
typedef long long ll;
template<typename T>
void read(T &x) {
int flag = 1; x = 0; char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); x *= flag;
}
const int N = 6e5 + 10;
int trie[N * 24][2], latest[N * 24];
int s[N], rt[N], n, m, tot;
void insert(int i, int k, int p, int q) { // q -> p s[i][k]
if(k < 0) { latest[q] = i; return ; }
int c = (s[i] >> k) & 1;
if(p) trie[q][c ^ 1] = trie[p][c ^ 1];
trie[q][c] = ++tot;
insert(i, k - 1, trie[p][c], trie[q][c]);
latest[q] = max(latest[trie[q][0]], latest[trie[q][1]]);
}
int query(int now, int val, int k, int limit) {
if(k < 0) return s[latest[now]] ^ val;
int c = (val >> k) & 1;
if(latest[trie[now][c ^ 1]] >= limit)
return query(trie[now][c ^ 1], val, k - 1, limit);
else return query(trie[now][c], val , k - 1, limit);
}
int main () {
read(n), read(m);
latest[0] = -1, rt[0] = ++tot;
insert(0, 23, 0, rt[0]);
for(int i = 1; i <= n; ++i) {
int x; read(x);
s[i] = s[i - 1] ^ x, rt[i] = ++tot;
insert(i, 23, rt[i - 1], rt[i]);
}
for(int i = 1; i <= m; ++i) {
char opt[3]; scanf("%s", opt);
if(opt[0] == 'A') {
int x; read(x);
rt[++n] = ++tot, s[n] = s[n - 1] ^ x;
insert(n, 23, rt[n - 1], rt[n]);
} else {
int l, r, x; read(l), read(r), read(x);
printf("%d\n", query(rt[r - 1], x ^ s[n], 23, l - 1));
}
}
return 0;
}