题面

给定一个非负整数序列$a$，初始长度为$n$。

有 $m$ 个操作，有以下两种操作类型：

1. A x：添加操作，表示在序列末尾添加一个数 $x$，序列的长度 $n+1$。
2. 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;	
}