注意点:
- 思想可以类比主席树.
#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=6e5,MAXM=6e5;
struct Node{
int son[2];
int latest;
}tr[MAXN*24];
int nodeCnt=0;
void insert(int p,int &q,int nowRoot,int val,int k){
if(!q)q=++nodeCnt;
tr[q].latest=nowRoot;
if(k<0)return;
bool c=(val>>k)&1;
tr[q].son[c^1]=tr[p].son[c^1];
insert(tr[p].son[c],tr[q].son[c],nowRoot,val,k-1);
}
int query(int now,int latest,int val,int k){
if(k<0)return tr[now].latest;
bool c=(val>>k)&1;
if(tr[tr[now].son[c^1]].latest>=latest)return query(tr[now].son[c^1],latest,val,k-1);
else return query(tr[now].son[c],latest,val,k-1);
}
int root[MAXN],b[MAXN],rootCnt=0;
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int tmp;
scanf("%d",&tmp);
rootCnt++;
b[rootCnt]=b[rootCnt-1]^tmp;
insert(root[rootCnt-1],root[rootCnt],rootCnt,b[rootCnt],25);
}
tr[0].latest=-1;
for(int i=1;i<=m;i++){
char opt[10];
scanf("%s",opt);
if(opt[0]=='A'){
int x;
scanf("%d",&x);
rootCnt++;
b[rootCnt]=b[rootCnt-1]^x;
insert(root[rootCnt-1],root[rootCnt],rootCnt,b[rootCnt],25);
}else if(opt[0]=='Q'){
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
int nowVal=b[rootCnt]^x;
int p=query(root[r-1],l-1,nowVal,25);
int ans=b[p]^nowVal;
printf("%d\n",ans);
}
}
return 0;
}