利用可持久化Trie树实现范围内取值异或最大值
如果标题没有表达清楚意思，可以看这里的题干：
然后根据异或的性质，异或一个数两次相当于没有异或，那么我们可以维护一个异或前缀和
有了异或前缀和之后我们就可以通过前缀和的形式O（1）提取出任意的一个异或区间出来
然后就可以把题目转化成这样的形式
求max(b[p]^b[n]^x) (l-1<=p<=r-1)
这里只有b[p]是不知道的，我们提前把序列的异或前缀和预处理出来之后插入到可持久化Tire树里面，又因为b[n]和x是定值，这就又转化成上一篇博文中描述的问题了
只不过这里插入到Trie树里面的东西不是独立的，而是一个整体，我们要从这个整体异或中提取出关键的那一个结果来，由于我们的p是限定了范围的，那么这就相当于对应了一系列的前缀和
范围内的每一个结果都是可行的，因此我们凭借着贪心的时候能取最大取最大的思路，如果在当前Trie树里得不到局部最优解，就跳跃到另一颗更优的Trie树上进行就好了
可持久化的思想就是每一个版本的树的儿子之间乱跳
1 #include<cstdio> 2 const int maxn=600005; 3 inline int read() 4 { 5 int x=0,f=1;char ch=getchar(); 6 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 8 return x*f; 9 } 10 int n,m; 11 int a[maxn],b[maxn],bin[30],root[maxn]; 12 struct Trie 13 { 14 int cnt; 15 int ch[maxn*24][2],sum[maxn*24]; 16 int insert(int x,int val) 17 { 18 int tmp,y; 19 tmp=y=++cnt; 20 for(int i=23;i>=0;i--) 21 { 22 ch[y][0]=ch[x][0]; 23 ch[y][1]=ch[x][1]; 24 sum[y]=sum[x]+1; 25 int t=val&bin[i];t>>=i; 26 x=ch[x][t]; 27 ch[y][t]=++cnt; 28 y=ch[y][t]; 29 } 30 sum[y]=sum[x]+1; 31 return tmp; 32 } 33 int query(int l,int r,int val) 34 { 35 int tmp=0; 36 for(int i=23;i>=0;i--) 37 { 38 int t=val&bin[i];t>>=i; 39 if(sum[ch[r][t^1]]-sum[ch[l][t^1]]) 40 tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1]; 41 else r=ch[r][t],l=ch[l][t]; 42 } 43 return tmp; 44 } 45 }trie; 46 int main() 47 { 48 bin[0]=1; 49 for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1; 50 n=read();m=read(); 51 n++; 52 for(int i=2;i<=n;i++) a[i]=read(); 53 for(int i=1;i<=n;i++) b[i]=b[i-1]^a[i]; 54 for(int i=1;i<=n;i++) 55 root[i]=trie.insert(root[i-1],b[i]); 56 char ch[5]; 57 int l,r,x; 58 while(m--) 59 { 60 scanf("%s",ch); 61 if(ch[0]=='A') 62 { 63 n++; 64 a[n]=read();b[n]=b[n-1]^a[n]; 65 root[n]=trie.insert(root[n-1],b[n]); 66 } 67 else 68 { 69 l=read();r=read();x=read(); 70 printf("%d ",trie.query(root[l-1],root[r],b[n]^x)); 71 } 72 } 73 return 0; 74 }