异或满足可减性,所以可以维护前缀和,然后
a[p] xor a[p + 1] xor ... xor a[n] xor = s[p - 1] xor s[n] xor
然后就只要维护s[]。添加很好维护,重点是如何查询
此时查询转变为:val = s[n] xor x,求一个p∈[l - 1, r - 1]使得s[p] xor val最大
可以构建一颗可持久化Trie,第i个版本为插入了s[i]后的Trie树。
每次查询,从根节点开始,贪心地选与这一位相反的值。
此外,还有一个l−1≤p≤r−1的限制。
先考虑p≤r−1,查询第r−1个版本的Trie即可,因为此时不可能访问到r-1r−1之后的ss。 再考虑l−1≤p,对每个节点维护一个latest值,表示子树中所有ss值的下标的最大值。这样,在查询时只访问latest≥l−1的节点就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 5;
struct Node {
int son[2], cnt;
}trie[maxn * 30];
int n, m, tot, ans, rt[maxn];
char opt[2];
void insert(int &x, int y, int d, int num) {
x = ++tot;
trie[x] = trie[y];
trie[x].cnt++;
if (d < 0) {
return ;
}
int t = num & (1 << d) ? 1 : 0;
insert(trie[x].son[t], trie[y].son[t], d - 1, num);
}
void query(int x, int y, int d, int num) {
if (d < 0) {
return ;
}
int t = num & (1 << d) ? 1 : 0;
int dl = trie[trie[x].son[t ^ 1]].cnt;
int dr = trie[trie[y].son[t ^ 1]].cnt;
if (dr - dl) {
ans |= (1<< d);
query(trie[x].son[t ^ 1], trie[y].son[t ^ 1], d - 1, num);
} else {
query(trie[x].son[t], trie[y].son[t], d - 1, num);
}
}
int main() {
scanf("%d%d", &n, &m);
n++;
int sum = 0, l, r, x;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
sum ^= x;
insert(rt[i], rt[i - 1], 24, sum);
}
while (m--) {
scanf("%s", opt);
if (opt[0] == 'A') {
scanf("%d", &x);
sum ^= x;
insert(rt[++n], rt[n], 24, sum);
} else {
scanf("%d%d%d", &l, &r, &x);
x ^= sum; ans = 0;
l++; r++;
query(rt[l - 2], rt[r - 1], 24, x);
printf("%d\n", ans);
}
}
return 0;
}