题目

给定一个非负整数序列{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 最大，输出最大是多少。

假设询问操作有 T个，则输出应该有 T行，每行一个整数表示询问的答案。

Constrain

N,M<=300000，0<=a[i]<=10^7。

题解

可持久化trie！

类似于xor longest path，但是加入了时间限制

$a[p] mathrm{xor} a[p+1] mathrm{xor} cdots mathrm{xor} a[N] mathrm{xor} x=a[N] mathrm{xor} a[p-1] mathrm{xor} x = a[N] mathrm{xor} x mathrm{xor} a[p-1]$

那么就只考虑时间限制

可以把trie树复制几次，但是空间不够用

只考虑指针，复制变成指向之前的版本，添加的节点新建就可以了，还要注意添加的节点也有复制之前的版本的部分。

这样就可以得到时间$leqslant$的部分

如果要$geqslant$，那就需要不走过于旧的节点，给每个节点记录一个创建时间就可以了。新的节点会走新的路径，不要去修改老的节点的创建时间。

AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
#include<cassert>
#define REP(i,a,b) for(register int i=(a); i<(b); i++)
#define REPE(i,a,b) for(register int i=(a); i<=(b); i++)
using namespace std;
typedef long long ll;
#define MAXN 300007
#define MAXV 10000000
#define ML 23
int trie[MAXN*2*ML][2], tn;
int r[MAXN*2], rn;
int la[MAXN*2*ML];
int n,m;
int now, ans;
inline void ins(int v) {
	int i=r[rn++]=tn++; memset(trie[i],-1,sizeof(trie[i])); //新建一个版本
	int j=-1;//上一个版本
	if(rn>1) { j=r[rn-2]; }
	for(int k=ML; k>=0; k--) {
		int V=v>>k&1;
		if(~j) {//如果存在上一个版本
			trie[i][V^1]=trie[j][V^1];	//不同的部分指向上一个版本的不同的部分（肯定没有变化）
			j=trie[j][V];	//与上一个版本的相同的部分也要考虑
		}
		int i_=trie[i][V]=tn++; memset(trie[i_],-1,sizeof(trie[i_]));	//新建子节点
		la[i_]=rn-1;
		i=i_;
	}
}
inline int que(int v, int f, int t) {
	int ans=0;
	int i=r[t];
	for(int k=ML; k>=0; k--) {
		int V=v>>k&1;
		if((~trie[i][V^1]) && la[trie[i][V^1]]>=f) {
			ans |= 1<<k;
			i=trie[i][V^1];
		} else {
			i=trie[i][V];
		}
	}
	return ans;
}
int main() {
	scanf("%d%d", &n, &m);rn=0; tn=0;
	ins(0); now=0;
	REP(i,0,n) {
		int a; scanf("%d", &a);
		now^=a;
		ins(now);
	}
	REP(i,0,m) {
		char ch; do ch=getchar(); while(ch<=' ');
		if(ch=='A') {
			int a; scanf("%d", &a);
			now^=a;
			ins(now);
		} else { //Q
			int f,t,v; scanf("%d%d%d", &f, &t, &v);
			f--;t--;	//实际是寻找s[p-1]
			v^=now;
			printf("%d
", que(v,f,t));
		}
	}
}