从 i 到 n 的异或和 = 从 1 到 n 的异或和 异或 从 1 到 i-1 的异或和
所以只要存 1 到 i-1 的异或和就行了
开一个可持久化字典树
从高位到低位，存每个从 1 ~ i 的异或和
询问 i 到 n 异或 x 就相当于询问 （1到n 的异或和 异或 x ）再异或 1到 i-1的异或和
1到n 的异或和 异或 x 我们是知道的
在字典树上异或时
只要贪心地优先走与当前位相反的节点就好了（因为是从高位到低位）
对于 l = 1 的情况特判一下就好了
可持久化字典树就像主席树一样，不难的
具体细节在代码里
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N=6e5+7; int n,m; int rt[N],cnt,c[N*27][2],num[N*27]; int sum[N]; inline void ins(int a,int b,int k,int x)//插入 //a是当前节点,b是上一个字典树的节点,插入到第k位,异或和为x { if(k<0) return; int u=(x>>k)&1;//找出当前位的数 c[a][!u]=c[b][!u];//另一边直接继承上一个树的节点 c[a][u]=++cnt;//这一边新开一个节点 num[cnt]=num[c[b][u]]+1;//经过当前节点的数量加1 ins(c[a][u],c[b][u],k-1,x);//向下插入 } inline int query(int a,int b,int k,int x)//查询 //a是1到l-1的字典树,b是1到r的字典树 { if(k<0) return 0; int u=(x>>k)&1; if(num[c[b][!u]]>num[c[a][!u]]) //如果大于，说明从l到r存在一个当前位为!u的前缀异或和 return (1<<k)+query(c[a][!u],c[b][!u],k-1,x);//贪心地选择这边 return query(c[a][u],c[b][u],k-1,x);//不然只能选另一边 } int main() { int a,l,r; cin>>n>>m; rt[0]=++cnt; ins(rt[0],0,26,0); for(int i=1;i<=n;i++) { scanf("%d",&a); sum[i]=sum[i-1]^a; rt[i]=++cnt; ins(rt[i],rt[i-1],26,sum[i]); } char s[5]; for(int i=1;i<=m;i++) { scanf("%s",s); if(s[0]=='A') { scanf("%d",&a); rt[++n]=++cnt; sum[n]=sum[n-1]^a; ins(rt[n],rt[n-1],26,sum[n]); } else { scanf("%d%d%d",&l,&r,&a); l--; r--;//l和r都要减1，因为是找异或前缀异或掉sum[n]前面的一部分 if(!l) printf("%d ",query(0,rt[r],26,a^sum[n]) );//对l特判一下 else printf("%d ",query(rt[l-1],rt[r],26,a^sum[n]) ); } } return 0; }