题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2741

题目分类：可持久化数据结构，分块

题意：

给出一个序列，求区间内最大异或和子串，强制在线。

题解：

使用可持久化字典树支持查询对于一个端点和一个区间的最大异或和子串。

然后分块，考虑记录每个块的开头到任意一个位置的询问结果，这样就可以根号下时间处理。

程序：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int ins[60];
inline void despose(int x)
{
	for (int i=1;i<=31;i++)
	{
		if(((1<<(i-1))&x)!=0)ins[i]=1;
		else ins[i]=0;
	}
}
struct functionaltrie
{
	int siz,st[3300000],chi[3300000][2],val[3300000];
	functionaltrie()
	{
		siz=1;
		st[0]=1;
	}
	inline void insertinit()
	{
		int tmp=1;
		for (int i=31;i>=1;i--)
		{
		//	printf("%d %d %d\n",i,ins[i],tmp);
			if(chi[tmp][ins[i]]==0)
			{
				siz++;
				chi[tmp][ins[i]]=siz;
			}
			tmp=chi[tmp][ins[i]];
		}
	}
	inline void insert(int x)
	{
		siz++;
		st[x]=siz;
		int tmp=siz,tmf=st[x-1];
		for (int i=31;i>=1;i--)
		{
		//	printf("%d %d %d\n",i,ins[i],tmp);
			siz++;
			chi[tmp][ins[i]]=siz;
			val[tmp]=1+val[tmf];
			chi[tmp][1-ins[i]]=chi[tmf][1-ins[i]];
			tmp=chi[tmp][ins[i]];
			tmf=chi[tmf][ins[i]];
		}
		val[tmp]=val[tmf]+1;
	}
	inline int query(int x,int y)
	{
		x++,y++;
		int tx=st[x],ty=st[y],ans=0;
	//	printf("--%d %d\n",x,y);
		for (int i=31;i>=1;i--)
		{  
		//	printf("--%d %d %d\n",tx,ty,ins[i]);
			if(val[chi[ty][1-ins[i]]]-val[chi[tx][1-ins[i]]]>0)
			{
				ans+=(1<<(i-1));
				tx=chi[tx][1-ins[i]];
				ty=chi[ty][1-ins[i]];	
			}
			else
			{
				tx=chi[tx][ins[i]];
				ty=chi[ty][ins[i]];
			}
		}return ans;
	}
}sgt;
int n,m,a[26000],len,par,x1,x2,lastans,num[26000],pos[26000],sta[26000],end[26000];
int pre[430][26000];
int main()
{
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]=(a[i-1]^a[i]);
		despose(a[i]); 
		sgt.insertinit();
	}
	despose(0);
	sgt.insertinit();
	sgt.insert(1);
	for (int i=1;i<=n;i++)
	{
		despose(a[i]);
		sgt.insert(i+1);
	}
	len=(int)sqrt(n);par=1;
	sta[1]=1;
	for (int i=1;i<=n;i++)
	{
		num[i]=num[i-1]+1;
		sta[i]=par;
		if(num[i]>len)
		{
			end[par]=i-1;
			par++;
			sta[par]=i;
			num[i]-=len;
		}pos[i]=par;
	}
	end[par]=n;
	for (int i=1;i<=par;i++)
	{
		pre[i][sta[i]]=0;
		for (int j=sta[i]+1;j<=n;j++)
		{
			despose(a[j]);
			pre[i][j]=max(pre[i][j-1],sgt.query(sta[i]-2,j));
		//	printf("%d %d %d\n",i,j,pre[i][j]);
		}
	}
	sta[par+1]=n+1;
	for (int i=1;i<=m;i++)
	{
		scanf("%d %d",&x1,&x2);
		x1=((long long)x1+(long long)lastans)%(long long)n+1LL;
		x2=((long long)x2+(long long)lastans)%(long long)n+1LL;
		if(x1>x2)swap(x1,x2);
		int tp=pos[x1]+1;//printf("%d---%d\n",x1,x2);
		if(pos[x1]==pos[x2])
		{
			int ans=0;
			for (int j=x1-1;j<x2;j++)
			{
				despose(a[j]);
				ans=max(ans,sgt.query(x1-2,x2));
			}printf("%d\n",ans);lastans=ans;
		}
		else
		{
			int ans=pre[tp][x2];//printf("%d %d %d\n",tp,x2,ans);
			for (int j=x1-1;j<sta[tp];j++)
			{
				despose(a[j]);
				ans=max(ans,sgt.query(x1-2,x2));
			}printf("%d\n",ans);lastans=ans;
		}
	}
	return 0;
}