[文章目录]
Description
给定一个非负整数序列 {a}，初始长度为 N。
有M个操作，有以下两种操作类型：
1 、A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N+1。
2 、Q l r x：询问操作，你需要找到一个位置 p，满足 l<=p<=r，使得：a[p] xor a[p+1] xor ... xor a[N] xor x 最大，输出最大是多少。
如果维护一个后缀的亦或和的话，发现这个东西随时在变，考虑转化成前缀的亦或和。后缀=前缀^S（S为这个序列的亦或和） => 找一个前缀亦或和，使得前缀^S^x最大。
用trie树维护所有的前缀的亦或和每一位上的值，将其可持久化，每个位置的trie是由上一个位置trie得来，然后在查询的时候进入r-1的trie树，判断当前节点的最近时间戳是否大于等于l-1，进行贪心。注意初始化空节点的时间戳和前缀没有元素的情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,tot,sum,rot[601000];
struct Trie
{
int c[2],id;
}t[20000000];
void insert(int id,int y,int z)
{
int p=++tot; rot[id]=tot; bool fl;
for(int i=24;~i;--i)
{
fl=(z>>i)&1;
t[p].c[fl^1]=t[y].c[fl^1];
t[p].c[fl]=++tot; t[tot].id=id;
p=t[p].c[fl]; y=t[y].c[fl];
}
}
int query(int x,int y,int z)
{
int re=0; bool fl;
for(int i=24;~i;--i)
{
fl=((z>>i)&1)^1;
if(t[t[x].c[fl]].id>=y) re|=(1<<i);
else fl^=1;
x=t[x].c[fl];
}
return re;
}
int main()
{
scanf("%d%d",&n,&m);
int x; t[0].id=-1;
insert(0,0,0);
for(int i=1;i<=n;++i)
{
scanf("%d",&x); sum^=x;
insert(i,rot[i-1],sum);
}
char sw[10]; int l,r;
while(m--)
{
scanf("%s",sw);
if(sw[0]=='A')
{
scanf("%d",&x); sum^=x;
++n; insert(n,rot[n-1],sum);
}
else
{
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",query(rot[r-1],l-1,x^sum));
}
}
return 0;
}