可持久化真是个神奇的东西，（当然一开始并未想到可以这样用）
每个数建一个trie，前缀xor和来求，b[i]为1~i的异或和，求b[p]^b[n]^x的最大值，用sum确认结点是否存在。然后贪心求xor最大值。写的时候把a[i]向后移一位。
1 /************************************************************** 2 Problem: 3261 3 User: zyhh 4 Language: C++ 5 Result: Accepted 6 Time:4084 ms 7 Memory:176604 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 #include 14 #include 15 #include 16 using namespace std;17 const int maxn=600005;18 const int inf=2147483647;19 int n,m;20 int bin[30],a[maxn],b[maxn],root[maxn];21 struct trie22 {23 int cnt;24 int ch[maxn*24][2],sum[maxn*24];25 int insert(int x,int val)26 {27 int tmp,y;tmp=y=++cnt;28 for(int i=23;i>=0;i--)29 {30 ch[y][0]=ch[x][0];ch[y][1]=ch[x][1];31 sum[y]=sum[x]+1;32 int t=val&bin[i];33 t>>=i;34 x=ch[x][t];35 ch[y][t]=++cnt;36 y=ch[y][t];37 }38 sum[y]=sum[x]+1;39 return tmp;40 }41 int query(int l,int r,int val)42 {43 int tmp=0;44 for(int i=23;i>=0;i--)45 {46 int t=val&bin[i];t>>=i;47 if(sum[ch[r][t^1]]-sum[ch[l][t^1]])48 tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1];49 else r=ch[r][t],l=ch[l][t];50 }51 return tmp;52 }53 }trie;54 template void read(T&x)55 {56 x=0;char c=getchar();int f=0;57 while(c<'0'||c>'9'){f|=(c=='-');c=getchar();}58 while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();59 x=f?-x:x;60 }61 int main()62 {63 bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;64 read(n);read(m);65 n++;66 for(int i=2;i<=n;i++)read(a[i]);67 for(int i=1;i<=n;i++)b[i]=b[i-1]^a[i];68 for(int i=1;i<=n;i++)root[i]=trie.insert(root[i-1],b[i]);69 char ch[5];70 int l,r,x;71 while(m--)72 {73 scanf("%s",ch);74 if(ch[0]=='A')75 {76 n++;77 read(a[n]);b[n]=b[n-1]^a[n];78 root[n]=trie.insert(root[n-1],b[n]);79 }80 else81 {82 read(l);read(r);read(x);83 printf("%d\n",trie.query(root[l-1],root[r],b[n]^x));84 }85 }86 return 0;87 }