程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj3261 最大異或和

bzoj3261 最大異或和

編輯:C++入門知識

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved