Description

多个询问l，r，求所有子区间异或和中最大是多少

强制在线

Solution

分块+可持久化trie

1.对于每块的左端点L，预处理出L到任意一个i，[L,j] 间所有子区间异或和中最大为多少,\(\Theta(n\sqrt n)\)

2.对于询问x,y:

①x,y属于同一块,O(\(\sqrt n log n\))直接扫

②x,y不属于同一块, 找到x右边第一块的左端点，用预处理求出左端点到y，剩下的直接扫,O(\(\sqrt n log n\))

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

using namespace std;

typedef long long LL;

const int M=12930;

const int B=30;

const int L=111;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar())if(c=='-')f=0;

	for(;isdigit(c);c=getchar())x=x*10+c-48;

	return x;

}

int n,m,sn;

int a[M];

int s[L][M];

int tot;

int ch[M*32][2];

int sz[M*32];

int root[M];

int F(int x){//写法取决于存法

	return x/sn;

}

int cpynode(int rt){

	tot++;

	ch[tot][0]=ch[rt][0];

	ch[tot][1]=ch[rt][1];

	sz[tot]=sz[rt]+1;

	return tot;

}

int ins(int rt,int d){

	int tmp,x,y,i,k;

	tmp=x=cpynode(rt);

	for(i=B;i>=0;i--){

		k=(d>>i)&1;

		y=cpynode(ch[x][k]);

		ch[x][k]=y;

		x=y;

	}

	return tmp;

}

int get(int lt,int rt,int d){

	int i,k,res=0;

	for(i=B;i>=0;i--){

		k=((d>>i)&1)^1;

		if(sz[ch[rt][k]]-sz[ch[lt][k]]>0)

			lt=ch[lt][k],rt=ch[rt][k],res+=(1<<i);

		else lt=ch[lt][k^1],rt=ch[rt][k^1];

	}

	return res;

}

int main(){

	int i,j;

	int x,y,z,st,ll,rr;

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

	sn=(int)sqrt(n);

	for(i=1;i<=n;i++) a[i]=a[i-1]^rd();

	root[0]=ins(root[0],0);

	for(i=1;i<=n;i++) root[i]=ins(root[i-1],a[i]);

	for(i=0;i<=n;i++) if(i%sn==0){//

		x=F(i);

		s[x][i]=0;

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

			s[x][j]=max(s[x][j-1],get(root[(i-1)>=0?(i-1):(n+1)],root[j-1],a[j]));

		}

	}

	int ans=0;

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

		ans%=n;

		ll=rd()%n,rr=rd()%n;

		x=min((ll+ans)%n+1,(rr+ans)%n+1);

		y=max((ll+ans)%n+1,(rr+ans)%n+1);

		x--;

		ans=0;

		if(F(x)==F(y)){

			//ans=a[y];这样写是错的

			for(j=x;j<y;j++) ans=max(ans,get(root[j],root[y],a[j]));

		}

		else{

			if(x%sn==0) z=F(x);//

			else z=F(x)+1;

			st=z*sn;//取决于存法

			ans=s[z][y];

			for(j=x;j<st;j++) ans=max(ans,get(root[j],root[y],a[j]));

		}

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

	}

	return 0;

}