可持久化01Trie树【p4735(bzoj3261)】最大异或和

Description

给定一个非负整数序列$\{a\}$，初始长度为$N$。

有$M$个操作，有以下两种操作类型：

A x：添加操作，表示在序列末尾添加一个数$x$，序列的长度$N+1$。

Q l r x：询问操作，你需要找到一个位置$p$，满足$l \leq p \leq r$，使得： $a[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x$ 最大，输出最大是多少。

Input

第一行包含两个整数 $N,M$，含义如问题描述所示。

第二行包含 $N$个非负整数，表示初始的序列$A$ 。

接下来 $M$行，每行描述一个操作，格式如题面所述。

Output

假设询问操作有 $T$ 个，则输出应该有 $T$ 行，每行一个整数表示询问的答案。

表示是个裸的可持久化$01Trie$树.

考虑到$\oplus$具有的性质$(x\ \oplus \ y) \oplus y=x$

所以我们最终所求就是$sum[p-1]\oplus sum[n] \oplus x $

(其中$sum$数组存储异或前缀和.)

想要求出最大值.我们显然已知$sum[n] \oplus x$

则要在$[l,r]$中找出与$sum[n]\oplus x$异或起来的最大值。

显然直接查询即可.

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

const int maxn=600009;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

struct Trie

{

	int ch[maxn*35][2],cnt[maxn*35],tot,root[maxn];

	Trie(){root[0]=tot=1;}

	inline void insert(R int lastroot,R int &nowroot,int x)

	{

		nowroot=++tot;

		int u=nowroot;

		for(R int i=30;~i;i--)

		{

			R int bit=(x>>i)&1;

			ch[u][!bit]=ch[lastroot][!bit];

			ch[u][bit]=++tot;

			u=ch[u][bit];

			lastroot=ch[lastroot][bit];

			cnt[u]=cnt[lastroot]+1;

		}

	}

	inline int query(R int l,R int r,R int x)

	{

		R int res=0;

		for(R int i=30;~i;i--)

		{

			R int bit=(x>>i)&1;

			if(cnt[ch[r][!bit]]-cnt[ch[l][!bit]])

			{

				l=ch[l][!bit];

				r=ch[r][!bit];

				res+=(1<<i);

			}

			else

			{

				l=ch[l][bit];

				r=ch[r][bit];

			}

		}

		return res;

	}

}se;

int n,m,sum[maxn],a[maxn];

char opt[5];

int main()

{

	in(n),in(m);n++;

	for(R int i=2,x;i<=n;i++)in(a[i]);

	for(R int i=1;i<=n;i++)sum[i]=sum[i-1]^a[i];

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

		se.insert(se.root[i-1],se.root[i],sum[i]);

	for(R int x,y,z;m;m--)

	{

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

		if(opt[1]=='A')

		{

			in(x);n++;

			sum[n]=sum[n-1]^x;

			se.insert(se.root[n-1],se.root[n],sum[n]);

		}

		else

		{

			in(x),in(y),in(z);

			printf("%d\n",se.query(se.root[x-1],se.root[y],sum[n]^z));

		}

	}

}

巴特西

可持久化01Trie树【p4735(bzoj3261)】最大异或和

Description

Input

Output

最新文章

热门文章