P4735 最大异或和

P4735 最大异或和

可持久化 01Trie 维护区间异或最大值板子题。

以下标为 root 的编号，每次询问 \([l,r]\) 中的所有数异或 \(x\) 的最大值就是到 Trie 上面去搜索，记录当前子树中的数的个数。

然后如果两个root对应树的当前 cnt 不一样，那么就证明这一位在这个区间当中出现过，那直接加上这一位的贡献再往下继续搜索即可。

注意 0 的特判。

代码：

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template <typename T>
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
const int N=1e6+1,M=3e7+1;
int ch[N*28][2],cnt[N*28],sum[N],rt[N],now,las,cur=1,top;
void Insert(int x,int pre,int k,int v){
	if(k<0) return ;
	int c=(v>>k)&1;
	ch[x][c^1]=ch[pre][c^1];
	ch[x][c]=++cur;
	cnt[ch[x][c]]=cnt[ch[pre][c]]+1;
	Insert(ch[x][c],ch[pre][c],k-1,v);
	return ;
}
int Query(int x,int pre,int k,int v){
	if(k<0) return 0;
	int c=(v>>k)&1;
	if(cnt[ch[pre][c^1]]>cnt[ch[x][c^1]]) return (1<<k)+Query(ch[x][c^1],ch[pre][c^1],k-1,v);
	return Query(ch[x][c],ch[pre][c],k-1,v);
}
int n,m;
signed main(){
	read(n),read(m);
	rt[0]=++cur;Insert(rt[0],0,25,0);top=n;
	for(int i=1,x;i<=n;i++) read(x),now^=x,rt[i]=++cur,Insert(rt[i],rt[i-1],25,now);
	for(int i=1;i<=m;i++){
		char op[5];int x,l,r;
		scanf("%s",op);
		if(op[0]=='A') read(x),now^=x,rt[++top]=++cur,Insert(rt[top],rt[top-1],25,now);
		else read(l),read(r),read(x),l--,r--,write(l?Query(rt[l-1],rt[r],25,x^now):Query(0,rt[r],25,x^now)),putchar('\n');
	}
	return 0;
}