【BZOJ2741】【FOTILE模拟赛】L 分块+可持久化Trie树

2022-09-20 20:50:09

【BZOJ2741】【FOTILE模拟赛】L

Description

FOTILE得到了一个长为N的序列A，为了拯救地球，他希望知道某些区间内的最大的连续XOR和。

即对于一个询问，你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj)，其中l<=i<=j<=r。

为了体现在线操作，对于一个询问(x,y)：

l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).
r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).

其中lastans是上次询问的答案，一开始为0。

Input

第一行两个整数N和M。

第二行有N个正整数，其中第i个数为Ai，有多余空格。

后M行每行两个数x,y表示一对询问。

Output

共M行，第i行一个正整数表示第i个询问的结果。

Sample Input

3 3
1 4 3
0 1
0 1
4 3

Sample Output

5
7
7

HINT

N=12000，M=6000，x,y,Ai在signed longint范围内。

题解：分块还是练脑子啊~

[a,b]最大连续xor和=[a-1,b]中任意两个前缀xor和的xor的最大值（就是求出前缀xor和数组s，找出a-1<=i<j<=b使得s[i]^s[j]最大）。

我们先枚举每个块的左端点i，然后枚举i右面的所有的j，求出[i,j]中任意两个前缀xor和的xor的最大值，这个可以用可持久化Trie树实现。那么对于询问[a,b]，我们已经处理完了[k*block,b]的答案，现在我们只需求出[a,k*block)中的答案。枚举然后一个一个在可持久化Trie树上找就行了。

一开始写着写着都快疯了，对拍时小数据全过，一到大数据就GG，最后不得已照着题解码一遍还是GG，最后发现数组开小了~

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

using namespace std;

const int maxn=12010;

typedef long long ll;

int n,m,B,tot;

int rt[maxn];

int ans;

int v[maxn],s[maxn],f[120][maxn];

struct Trie

{

	int siz,ch[2];

}tr[750000];

int rd()

{

	int ret=0;	char gc=getchar();

	while(gc<'0'||gc>'9')	gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret;

}

void insert(int x,int y,int num)

{

	int i,d;

	rt[y]=++tot,y=rt[y];

	for(i=1<<30;i;i>>=1)

	{

		d=((num&i)>0);

		tr[y].ch[d]=++tot,tr[y].ch[d^1]=tr[x].ch[d^1];

		y=tr[y].ch[d],x=tr[x].ch[d],tr[y].siz=tr[x].siz+1;

	}

}

int query(int x,int y,int num)

{

	int i,ret=0,d;

	x=(x<0)?0:rt[x],y=(y<0)?0:rt[y];

	for(i=1<<30;i;i>>=1)

	{

		d=!(num&i);

		if((tr[tr[y].ch[d]].siz-tr[tr[x].ch[d]].siz)>0)	ret|=i;

		else	d^=1;

		y=tr[y].ch[d],x=tr[x].ch[d];

	}

	return ret;

}

int main()

{

	//freopen("bz2741.in","r",stdin);

	//freopen("bz2741.out","w",stdout);

	n=rd(),m=rd();

	int i,j,c,d,a,b;

	insert(0,rt[0],0);

	for(i=1;i<=n;i++)	v[i]=rd(),s[i]=s[i-1]^v[i],insert(rt[i-1],i,s[i]);

	B=int(sqrt(double(n)));

	for(i=0;i*B<=n;i++)	for(j=i*B;j<=n;j++)	f[i][j]=max(query(i*B-1,j,s[j]),j?f[i][j-1]:0);

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

	{

		a=((ll)rd()+ans)%n+1,b=((ll)rd()+ans)%n+1,ans=0;

		if(a>b)	swap(a,b);

		a--,c=a/B+1,ans=f[c][b];

		for(j=min(c*B-1,b);j>=a;j--)	ans=max(ans,query(a-1,b,s[j]));

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

	}

	return 0;

}

码农公寓