You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
70 lines
1.7 KiB
70 lines
1.7 KiB
#include <cstdio>
|
|
#include <cstring>
|
|
#include <algorithm>
|
|
#include <iostream>
|
|
#include <cmath>
|
|
|
|
using namespace std;
|
|
|
|
const int N = 6e5 + 10, M = 25 * N;
|
|
int s[N];
|
|
int tr[M][2], ver[M];
|
|
int root[N], idx;
|
|
|
|
void insert(int k, int p, int q) {
|
|
for (int i = 23; ~i; i--) {
|
|
int u = s[k] >> i & 1;
|
|
tr[q][u ^ 1] = tr[p][u ^ 1]; //复制
|
|
tr[q][u] = ++idx; //创建
|
|
ver[tr[q][u]] = k; //记录版本
|
|
q = tr[q][u], p = tr[p][u];
|
|
}
|
|
}
|
|
|
|
int query(int p, int l, int c) {
|
|
for (int i = 23; ~i ; i--) {
|
|
int u = c >> i & 1;
|
|
if (tr[p][u ^ 1] && ver[tr[p][u ^ 1]] >= l)
|
|
p = tr[p][u ^ 1];
|
|
else
|
|
p = tr[p][u];
|
|
}
|
|
return c ^ s[ver[p]]; // p:最终停留在的异或和最大值终点处,ver[p]这是哪个版本放进来的？,s[ver[p]]=S_{p-1}
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
int n, m;
|
|
cin >> n >> m;
|
|
|
|
// 0号版本,用于处理类似于S[1]-S[0]这样的递推边界值
|
|
root[0] = ++idx;
|
|
insert(0, 0, root[0]);
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
int x;
|
|
cin >> x;
|
|
root[i] = ++idx;
|
|
s[i] = s[i - 1] ^ x; //原数组不重要，异或前缀和数组才重要
|
|
insert(i, root[i - 1], root[i]);
|
|
}
|
|
|
|
while (m--) {
|
|
char op;
|
|
cin >> op;
|
|
if (op == 'A') {
|
|
int x;
|
|
cin >> x;
|
|
n++;
|
|
|
|
root[n] = ++idx;
|
|
s[n] = s[n - 1] ^ x;
|
|
insert(n, root[n - 1], root[n]);
|
|
} else {
|
|
int l, r, x;
|
|
cin >> l >> r >> x;
|
|
printf("%d\n", query(root[r - 1], l - 1, s[n] ^ x));
|
|
}
|
|
}
|
|
return 0;
|
|
} |