bzoj3261 最大異或和

bzoj3261 最大異或和

Description

給定一個非負整數序列 {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 最大，輸出最大是多少。

Input

第一行包含兩個整數 N ，M，含義如問題描述所示。
第二行包含 N個非負整數，表示初始的序列 A 。

接下來 M行，每行描述一個操作，格式如題面所述。

Output

假設詢問操作有 T個，則輸出應該有 T行，每行一個整數表示詢問的答案。

Sample Input

5 5
2 6 4 3 6
A 1
Q 3 5 4
A 4
Q 5 7 0
Q 3 6 6
對於測試點 1-2，N,M<=5 。

對於測試點 3-7，N,M<=80000 。
對於測試點 8-10，N,M<=300000 。

其中測試點 1, 3, 5, 7, 9保證沒有修改操作。
對於 100% 的數據， 0<=a[i]<=10^7。

Sample Output

4
5
6

HINT

對於100%的數據，0<=a[i]<=10^7。

Source

可持久化Trie樹第一題。

首先我們可以維護前綴異或和（這裡充分利用了異或的性質），然後就是求x^sum[n]^sum[p-1]的最大值。又因為x^sum[n]是定值，所以在Trie樹上貪心即可。

考慮到p是在區間[l-1,r-1]內的，所以我們不能對於每次詢問建一個Trie樹。但是我們可以對於Trie樹維護前綴和，建立可持久化Trie樹。這樣每次詢問，只要在trie[r-1]-trie[l-1]上貪心就可以了。

還有兩點需要注意的：

1.一開始要插入一個數0，因為最初異或和等於0。

2.對於每個點要維護一個id，這樣便於詢問操作中判斷該節點是否在區間[l-1,r-1]內。特別地，id[0]=1，這保證了空節點不會被訪問。(詳見代碼)

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 600005
#define maxm 20000005
using namespace std;
int n,m,tot=0,sum=0;
int rt[maxn],id[maxm],t[maxm][2];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void insert(int pre,int x,int k)
{
	int now=rt[k]=++tot;id[tot]=k;
	D(i,24,0)
	{
		int j=(x>>i)&1;
		t[now][j^1]=t[pre][j^1];
		t[now][j]=++tot;id[tot]=k;
		now=t[now][j];pre=t[pre][j];
	}
}
inline int query(int l,int r,int x)
{
	int ans=0,tmp=rt[r];
	D(i,24,0)
	{
		if (id[tmp]>i)&1)^1;
		if (id[t[tmp][j]]>=l) ans|=(1<'Z') ch=getchar();
		if (ch=='A')
		{
			sum^=read();
			insert(rt[n],sum,n+1);
			n++;
		}
		else
		{
			int l=read(),r=read(),x=read();
			printf("%d\n",query(l-1,r-1,sum^x));
		}
	}
	return 0;
}