题目描述
给定一个非负整数序列 ({a})，初始长度为(n)。
有 (m) 个操作，有以下两种操作类型：
(A x)：添加操作，表示在序列末尾添加一个数 (x)，序列的长度 (n+1)。
(Q l r x)：询问操作，你需要找到一个位置 (p)，满足(l le p le r)，使得： (a[p] oplus a[p+1] oplus ... oplus a[N] oplus x)最大，输出最大是多少。
输入格式
第一行包含两个整数 (N,M)，含义如问题描述所示。
第二行包含 (N)个非负整数，表示初始的序列 (A) 。
接下来 (M) 行，每行描述一个操作，格式如题面所述。
输出格式
假设询问操作有 (T) 个，则输出应该有 (T) 行，每行一个整数表示询问的答案。
输入输出样例
输入 #1
5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
输出 #1
4
5
6
说明/提示
对于测试点 (1−2)，(N,M le 5)。
对于测试点 (3−7)，(N,M le 80000)。
对于测试点 (8−10)，(N,M le 300000)。
其中测试点 (1,3,5,7,9)保证没有修改操作。
(0 le a[i] le 10^7)。
分析
其实这题的 (Trie) 树可以不用可持久化
因为前缀会有一些奇奇怪怪的特判，所以我的 (Trie) 树里存的是后缀
要满足 (a[p] xor a[p+1] xor ... xor a[N] xor x) 最大
不妨设后缀异或和为 (sum)
那么就有 $ sum_{i=p}^N sum[i] xor x$ 最大
单次操作可以用 (Trie) 树 实现
对于多组询问，我们只需要按照每一次询问的右端点从小到大离线排序即可
对于左端点，我们记录一下在 (Trie) 树中这个节点最晚在哪一次操作中被加入即可
常数比可持久化 (Trie) 树小不少，目前是最优解
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=6e5+5,maxk=34;
int a[maxn],sum[maxn],n,m,ans[maxn],cnt,top;
char s[maxn];
struct asd{
int l,r,id,val;
}b[maxn];
bool cmp(asd aa,asd bb){
return aa.r<bb.r;
}
int tr[maxn*10][2],mmax[maxn*10][2];
void ad(rg int val,rg int id){
rg int now=0;
for(rg int i=30;i>=0;i--){
rg int k=(val>>i)&1;
if(!tr[now][k]){
tr[now][k]=++cnt;
mmax[now][k]=id;
} else {
mmax[now][k]=std::max(mmax[now][k],id);
}
now=tr[now][k];
}
}
int cx(rg int val,rg int id){
rg int now=0,nans=0;
for(rg int i=30;i>=0;i--){
rg int k=(val>>i)&1;
if(tr[now][k^1] && mmax[now][k^1]>=id){
now=tr[now][k^1];
nans+=(1<<i);
} else {
now=tr[now][k];
}
}
return nans;
}
int main(){
n=read(),m=read();
for(rg int i=1;i<=n;i++){
a[i]=read();
}
rg int aa,bb,cc;
for(rg int i=1;i<=m;i++){
scanf("%s",s);
if(s[0]=='A'){
aa=read();
a[++n]=aa;
} else {
aa=read(),bb=read(),cc=read();
top++;
b[top].l=aa,b[top].r=bb,b[top].val=n,b[top].id=cc;
}
}
for(rg int i=n;i>=1;i--){
sum[i]=sum[i+1]^a[i];
}
for(rg int i=1;i<=top;i++){
b[i].val=sum[b[i].val+1]^b[i].id;
b[i].id=i;
}
std::sort(b+1,b+1+top,cmp);
rg int head=1;
for(rg int i=1;i<=top;i++){
while(head<=b[i].r){
ad(sum[head],head);
head++;
}
ans[b[i].id]=cx(b[i].val,b[i].l);
}
for(rg int i=1;i<=top;i++){
printf("%d
",ans[i]);
}
return 0;
}