题目描述：这里
可持久化字典树裸题，可以作为模板使用
首先介绍一下可持久化字典树
可持久化字典树，顾名思义，就是一种可持久化的数据结构，常用于处理异或问题
我们看一下题目，发现要求一个最大异或和，但是这个最大异或和很特殊，有一个区间的限制
首先，对于异或和问题，我们一般利用异或的前缀和性质，把一个区间的异或和变成两个值的异或
于是问题就转化为，在[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[];
int ed;
}tree[];
int s[];
int rt[];
int n,m;
int tot=;
char ch[];
void ins(int x,int num,int las)
{
rt[num]=++tot;
int now=rt[num],last=rt[las];
for(int i=;i>=;i--)
{
tree[now].to[]=tree[last].to[];
tree[now].to[]=tree[last].to[];
tree[now].ed=tree[last].ed+;
if((<<i)&x)tree[now].to[]=++tot,now=tree[now].to[],last=tree[last].to[];
else tree[now].to[]=++tot,now=tree[now].to[],last=tree[last].to[];
}
tree[now].ed=tree[last].ed+;
}
int query(int lq,int rq,int x)
{
int ret=;
int l=rt[lq],r=rt[rq];
for(int i=;i>=;i--)
{
if(x&(<<i))
{
if(tree[tree[r].to[]].ed-tree[tree[l].to[]].ed)ret|=(<<i),l=tree[l].to[],r=tree[r].to[];
else l=tree[l].to[],r=tree[r].to[];
}else
{
if(tree[tree[r].to[]].ed-tree[tree[l].to[]].ed)ret|=(<<i),l=tree[l].to[],r=tree[r].to[];
else l=tree[l].to[],r=tree[r].to[];
}
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
n++;
ins(,,);
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
s[i]=s[i-]^x;
ins(s[i],i,i-);
}
for(int i=;i<=m;i++)
{
scanf("%s",ch);
if(ch[]=='A')
{
int x;
scanf("%d",&x);
n++;
s[n]=s[n-]^x;
ins(s[n],n,n-);
}else
{
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
int s1=x^s[n];
printf("%d\n",query(l-,r,s1));
}
}
return ;
}