a[1] xor a[2] xor a[3] xor…xor a[p-2] xor a[p-1] xor a[p] xor…xor a[n]
利用前缀和
s[p] = a[1] xor a[2] xor a[3] xor…xor a[p-2] xor a[p-1] xor a[p]
ans = a[p] xor a[p+1]… xor a[n] = s[p-1] xor s[n]^x
设 v = s[n]^x => ans = s[p-1] xor v
L<=P<=R => L-1<=P-1<=R-1
记录每个版本的tire 在[L-1,R-1]的区间反向查找v,并记录数值。
#include<iostream>
#include<queue>
#include<cstring>
#define ios ios::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
const int N = 6e5+10;
int T;
int n,m;
const int len = 25;
int ch[N*len][2],x;
int root[N],s[N],idx,ver[N*len];
void insert(int x,int y,int i){
ver[x] = i;
for(int k=len;k>=0;k--){
int c = s[i]>>k&1;
ch[x][!c] = ch[y][!c];
ch[x][c] = ++idx;
x = ch[x][c],y = ch[y][c];
ver[x] = i;
}
}
int query(int x,int l,int v){
int res = 0;
for(int k=len;k>=0;k--){
int c = v>>k&1;
if(ver[ch[x][!c]]>=l)
x = ch[x][!c],res+=1<<k;
else x = ch[x][c];
}
return res;
}
int main(){
ios;cin>>n>>m;
ver[0] = -1;
root[0] = ++idx;
insert(root[0],0,0);
for(int i=1;i<=n;i++){
cin>>x;
s[i] = s[i-1]^x;
root[i] = ++idx;
insert(root[i],root[i-1],i);
}
for(int j=1,i=n;j<=m;j++){
char op;
int l,r;
cin>>op;
if(op == 'A'){
i++;
cin>>x;
root[i] = ++idx;
s[i] = s[i-1]^x;
insert(root[i],root[i-1],i);
}
else{
cin>>l>>r>>x;
cout<<query(root[r-1],l-1,s[i]^x)<<"\n";
}
}
return 0;
}