记录编号	560088	评测结果	AAWWWEWWWE
题目名称	[BZOJ 3261]最大区间异或和	最终得分	20
用户昵称	tat	是否通过	未通过
代码语言	C++	运行时间	1.423 s
提交时间	2021-04-09 21:29:10	内存使用	21.67 MiB

#include <bits/stdc++.h>
using namespace std;
//可持久化trie 
int n,m,s[600001]={0};
int rem[600001][34];
struct node{
	int da;
	node *son[2];
	int end,late;
	node(){
		da=0; end=-1;   //end 可以限制范围   表示是第几个字符串 
		memset(son,0,sizeof(son));
		late=-1;
	}
}*root[600001];  
void insert(int x){
	root[x]=new node();
	node *p1=root[x],*p2=root[x-1];
	for(int i=1;i<=32;i++){
		if(p2!=NULL){
			for(int j=0;j<=1;j++){
				if(p2->son[j]!=NULL){
					p1->son[j]=p2->son[j];
				}
			}
		}//这一步就是可持久化的结构 
		
	 	p1->son[rem[x][i]]=new node();//这一步往下接着走
		p1->son[rem[x][i]]->late=x;
	 	//而且是即使原来的trie 已经有节点了 也要接着建 
		p1=p1->son[rem[x][i]];
		if(p2==NULL)continue;
		if(p2->son[rem[x][i]]!=NULL){
			p2=p2->son[rem[x][i]];
		}
		else {
			p2=NULL; 
		}
	}
	p1->end=x;//记录树的编号 
}
int query(int y,int l,int r,int x){
	//l--; r--;
	if(r==0){
		return s[n]^x;
	}
	node *p=root[r];
	int val=s[n]^x  ,  tmp[33]={0}  ,rec[33]={0};
	for(int i=32;i>=1;i--){
		tmp[i]=val&1;
		val=val>>1;	
	}
	for(int i=1;i<=32;i++){
		int jud=0;
		if(tmp[i]==0)jud=1;
			else jud=0;
		if(p->son[jud]!=NULL&&p->son[jud]->late>=l){
			rec[i]=1;
			p=p->son[jud];
		}	//尽量让两个数相同位的不一样 
			else if(p->son[tmp[i]]!=NULL&&p->son[tmp[i]]->late>=l){
			p=p->son[tmp[i]];
		    }//至少存在比序号l大的数 
				else break;
	}
	int sum=1; int ret=rec[32];
	for(int i=31;i>=1;i--){
		sum*=2;
		if(rec[i])ret+=sum;
	}
	return ret;
}
int main(int argc, char** argv) {
	freopen("xorsum.in","r",stdin);
	freopen("xorsum.out","w",stdout);
	cin>>n>>m;
	root[0]=NULL;
	for(int i=1;i<=n;i++){
		int a; cin>>a;
		s[i]=s[i-1]^a;
		a=s[i];
		for(int j=32;j>=1;j--){
			rem[i][j]=(a&1);
			a=a>>1;    //转化成二进制 
		}
		insert(i); 
	}
	for(int i=1;i<=m;i++){
		char k;
		cin>>k;
		if(k=='A'){
			n++; int a; 
			cin>>a; s[n]=s[n-1]^a;
			a=s[n];
			for(int j=32;j>=1;j--){
				rem[n][j]=(a&1);
				a=a>>1;    //转化成二进制 
			}
			insert(n); 
		}
		if(k=='Q'){
			int a,b,c;
			cin>>a>>b>>c;
			int ans=0;
			for(int j=1;j<=n;j++){
				ans=max(ans,query(j,a-1,b-1,c));
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}