BZOJ3261：最大异或和

浅谈\(Trie\)：https://www.cnblogs.com/AKMer/p/10444829.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=3261

假设现在所有数的异或和是\(xor\_sum\)，\(sum\_xor[i]\)表示前\(i\)个数的异或和，那么每次询问可以转化成：

在区间\([l-1,r-1]\)里面找一个\(sum\_xor_i\)，使得\(sum\_xor_i\oplus x\oplus xor\_sum\)最大值。

我们已经知道了\(x\oplus xor\_sum\)的值，只需要按照每一位去贪心地找\(sum\_xor_i\)的合适的值就行了。

由于是在区间内找有没有某一位存在我想要的，显然就能想到可持久化了。

时间复杂度：\(O((n+m)*24)\)

空间复杂度：\(O((n+m)*24)\)

代码如下：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=3e5+5;

char s[5];

int rt[maxn<<1];

int cnt,n,m,xor_sum;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct Trie {

	int tot;

	struct node {

		int sum;

		int son[2];

	}p[maxn*48];

	void ins(int lst_id,int id,int v) {

		int lst=rt[lst_id],u;

		u=rt[id]=++tot;

		for(int i=24;~i;i--) {

			int c=v>>i&1;

			p[u].son[c]=++tot;

			u=p[u].son[c],lst=p[lst].son[c];

			p[u]=p[lst];p[u].sum++;

		}

	}

	void make_ans(int u2,int u1,int v) {

		int ans=0;

		for(int i=24;~i;i--) {

			int c=v>>i&1;

			int sum=p[p[u1].son[c^1]].sum;

			sum-=p[p[u2].son[c^1]].sum;

			if(!sum)ans=ans<<1,u1=p[u1].son[c],u2=p[u2].son[c];

			else ans=ans<<1|1,u1=p[u1].son[c^1],u2=p[u2].son[c^1];

		}

		printf("%d\n",ans);

	}

}T;

int main() {

	cnt=n=read(),m=read();

	for(int i=1;i<=n;i++) {

		int x=read();xor_sum^=x;

		T.ins(i-1,i,xor_sum);

	}

	for(int i=1;i<=m;i++) {

		scanf("%s",s+1);

		if(s[1]=='A') {

			int x=read();xor_sum^=x,cnt++;

			T.ins(cnt-1,cnt,xor_sum);

		}

		else {

			int l=read(),r=read(),x=read();

			if(r==1) {printf("%d\n",x^xor_sum);continue;}

			T.make_ans(rt[max(0,l-2)],rt[r-1],x^xor_sum);

		}

	}

	return 0;

}