题目描述：这里
可持久化字典树裸题，可以作为模板使用
首先介绍一下可持久化字典树
可持久化字典树，顾名思义，就是一种可持久化的数据结构，常用于处理异或问题
我们看一下题目，发现要求一个最大异或和，但是这个最大异或和很特殊，有一个区间的限制
首先，对于异或和问题，我们一般利用异或的前缀和性质，把一个区间的异或和变成两个值的异或
于是问题就转化为，在[l,r]区间内求一个位置y,使$s_y xor s_n xor x$值最大
然后分析一下，不难想到，对于一般的最大异或问题，我们可以用01trie解决
但是此题中有区间限制，所以一般的01trie就难以使用了
这样我们引入可持久化字典树
可持久化字典树与普通字典树最大区别就在于，每次不是在原字典树上插入新的字符串，而是重建一棵字典树，然后将没有改变的信息与上一棵树共享
（也就是主席树的思想哈）
那么，在这里我们就构造一棵可持久化字典树（构造过程见代码，与主席树十分类似），然后进行查询即可
查询时，我们将$sn xor x$当成整体进行查询，然后像在正常的01trie上从高位向低位查找，首先查找这一位上是否可以放上不同的数，这里很好办，只需要在r和l-1上作差即可
这样就结束了
还有一个要点：对于异或和类的问题，我们要在将原序列整体右移一位，然后在空出来的首位补一个0！！！
为什么？
我们查询的是区间[l,r]，而我们知道，$s[n]^s[m]$代表的是[m+1,n]的异或和！
所以，当我们把问题转化为求两个数的异或最大值时，我们事实上也应该把区间改成[l-1,r-1]！
可是，如果我们把询问区间改成了[l-1,r-1]，我们在计算的时候，实际应当用的是[l-2,r-1]！
这又是为什么？
因为我们在计算时，计算方法是用区间右端点减区间左端点，可区间左端点也在区间内啊！
因此我们实际应该将左端点再向左移一位
可是哪有那么多位可移啊！万一给的l是1呢？
所以我们在首位补一个，这样就能保证查找时的正确性了。
贴代码：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> using namespace std; struct Trie { int to[2]; int ed; }tree[20000005]; int s[600005]; int rt[600005]; int n,m; int tot=0; char ch[2]; void ins(int x,int num,int las) { rt[num]=++tot; int now=rt[num],last=rt[las]; for(int i=25;i>=0;i--) { tree[now].to[0]=tree[last].to[0]; tree[now].to[1]=tree[last].to[1]; tree[now].ed=tree[last].ed+1; if((1<<i)&x)tree[now].to[1]=++tot,now=tree[now].to[1],last=tree[last].to[1]; else tree[now].to[0]=++tot,now=tree[now].to[0],last=tree[last].to[0]; } tree[now].ed=tree[last].ed+1; } int query(int lq,int rq,int x) { int ret=0; int l=rt[lq],r=rt[rq]; for(int i=25;i>=0;i--) { if(x&(1<<i)) { if(tree[tree[r].to[0]].ed-tree[tree[l].to[0]].ed)ret|=(1<<i),l=tree[l].to[0],r=tree[r].to[0]; else l=tree[l].to[1],r=tree[r].to[1]; }else { if(tree[tree[r].to[1]].ed-tree[tree[l].to[1]].ed)ret|=(1<<i),l=tree[l].to[1],r=tree[r].to[1]; else l=tree[l].to[0],r=tree[r].to[0]; } } return ret; } int main() { scanf("%d%d",&n,&m); n++; ins(0,1,0); for(int i=2;i<=n;i++) { int x; scanf("%d",&x); s[i]=s[i-1]^x; ins(s[i],i,i-1); } for(int i=1;i<=m;i++) { scanf("%s",ch); if(ch[0]=='A') { int x; scanf("%d",&x); n++; s[n]=s[n-1]^x; ins(s[n],n,n-1); }else { int l,r,x; scanf("%d%d%d",&l,&r,&x); int s1=x^s[n]; printf("%d ",query(l-1,r,s1)); } } return 0; }