因为在后面加数字又求后缀和太麻烦，所以xor[p…n]=xor[1…n]^xor[p-1…n]。
首先处理出来区间异或前缀和，对前缀和建trie树（在最前面放一棵0表示最开始的前缀和
然后就是可持久化trie的板子了
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
int n,m,a[N],b[N],rt[N],cnt;
char c[];
struct qwe
{
int c[],sum;
}t[N*];
int read()
{
int r=;
char p=getchar();
while(p>''||p<'')
p=getchar();
while(p>=''&&p<='')
{
r=r*+p-;
p=getchar();
}
return r;
}
int add(int x,int v)
{
int tmp=++cnt,y=cnt;
for(int i=;i>=;i--)
{
t[y].c[]=t[x].c[];
t[y].c[]=t[x].c[];
t[y].sum=t[x].sum+;
int q=(v&(<<i))>>i;
x=t[x].c[q];
t[y].c[q]=++cnt;
y=t[y].c[q];
}
t[y].sum=t[x].sum+;
return tmp;
}
int ques(int l,int r,int v)
{
int re=;
for(int i=;i>=;i--)
{
int q=(v&(<<i))>>i;
if(t[t[r].c[q^]].sum-t[t[l].c[q^]].sum)
re+=(<<i),l=t[l].c[q^],r=t[r].c[q^];
else
l=t[l].c[q],r=t[r].c[q];
}
return re;
}
int main()
{
n=read(),m=read();
n++;
for(int i=;i<=n;i++)
a[i]=read();
for(int i=;i<=n;i++)
b[i]=b[i-]^a[i];
for(int i=;i<=n;i++)
rt[i]=add(rt[i-],b[i]);
while(m--)
{
scanf("%s",c);
if(c[]=='A')
{
a[++n]=read();
b[n]=b[n-]^a[n];
rt[n]=add(rt[n-],b[n]);
}
else
{
int l=read(),r=read(),x=read();
printf("%d\n",ques(rt[l-],rt[r],b[n]^x));
}
}
return ;
}
/*
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
*/
