题面
给定一个非负整数序列$a$,初始长度为$n$。
有 $m$ 个操作,有以下两种操作类型:
A x
:添加操作,表示在序列末尾添加一个数 $x$,序列的长度 $n+1$。Q l r x
:询问操作,你需要找到一个位置 $p$,满足$l \leq p \leq r$,使得: $a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus x$ 最大,输出最大是多少。
思路
小清新可持久化trie树题。
考虑维护后缀和然后再用可持久化trie树查询,发现1操作不大好做,因为会影响前面所有的后缀和。那么考虑异或性质,对2操作进行变形。设$sum[N]=a[1] \oplus a[2] \oplus \ldots \oplus a[N]$我们发现$a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus x$=$sum[N]\oplus sum[N]\oplus a[p] \oplus a[p+1] \oplus \ldots \oplus a[N] \oplus x$发现后面$p+1$到$N$那一段$a$全被异或掉了,就可以变形为$sum[p-1]$,那么式子变化为$sum[p-1]\oplus sum[N] \oplus x$,注意询问时$l-1$,$r-1$然后考虑下边界特判就好了。
代码
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline void read(int &x)
{
int f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
void print(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);}
putchar(x%10+'0');
}
int N,M,sum=0,rt[4*300005],cnt=0;
struct trie{int ls,rs,size;}tree[80*300005];
inline void insert(int pre,int &root,int i,int x)
{
root=++cnt;
tree[root]=tree[pre];
tree[root].size++;
if (i<0) return;
if ((x>>i)&1) insert(tree[pre].rs,tree[root].rs,i-1,x);
else insert(tree[pre].ls,tree[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{
if (pre==root) return x;
if (i<0) return 0;
if ((x>>i)&1)
{
if (tree[tree[root].ls].size-tree[tree[pre].ls].size>=1) return query(tree[pre].ls,tree[root].ls,i-1,x)+(1<<i);
else return query(tree[pre].rs,tree[root].rs,i-1,x);
}
else
{
if (tree[tree[root].rs].size-tree[tree[pre].rs].size>=1) return query(tree[pre].rs,tree[root].rs,i-1,x)+(1<<i);
else return query(tree[pre].ls,tree[root].ls,i-1,x);
}
}
int main()
{
read(N),read(M);
for (int a,i=1;i<=N;i++) read(a),sum^=a,insert(rt[i-1],rt[i],30,sum);
for (int l,r,x,i=1;i<=M;i++)
{
char s[10];
scanf("%s",s+1);
if (s[1]=='A') read(l),sum^=l,insert(rt[N],rt[N+1],30,sum),N++;
else
{
read(l),read(r),read(x);
l--,r--;
print(query(rt[max(l-1,0)],rt[r],30,x^sum));
putchar('\n');
}
}
return 0;
}