题面

$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$。

思路

本题是在区间里面找区间，直接做比较困难，那么让我们从简单开始：假如询问一个序列中的区间异或和最大，那么该怎么做，不难发现只要将序列的前缀异或和加入$trie$树中然后对于每个前缀查一次与它异或的最大值即可。那么此时拓展到了区间，不是一整段序列了，怎么办？考虑分块，$f[i][j]$表示从第$i$块起点开始到$j$的区间最大连续异或和，这个玩意显然是可以$O(Nsqrt(N))$推得的，那么预处理出$f[i][j]$后对于一个没有跨块的询问直接暴力，对于跨块的询问暴力查询左边边角即可，不过要从$l-1$开始，因为开头可选，然后和$f[num[l]+1][r]$比较即可。

代码

#include<bits/stdc++.h>
#define LL long long
#define Maxn 12005
using namespace std;
LL num[Maxn],N,M,sum[Maxn],rt[Maxn],len,tot,f[1025][Maxn],cnt=0,o;
LL lastans=0;
struct trie{LL ls,rs,size;}tree[300*Maxn];
struct block{LL l,r;}b[1025];
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void insert(LL pre,LL &root,LL i,LL x)
{
	root=++cnt; 
	tree[root]=tree[pre];
	tree[root].size++;
	if (i<0) return; 
	if ((x>>i)&1) insert(tree[pre].rs,tree[root].rs,i-1,x);
	else insert(tree[pre].ls,tree[root].ls,i-1,x);
}
inline LL query(LL pre,LL root,LL i,LL x)
{
	if (i<0) return 0;
	if ((x>>i)&1)
	{
		if (tree[tree[root].ls].size-tree[tree[pre].ls].size>=1) return query(tree[pre].ls,tree[root].ls,i-1,x)+(1<<i);
		else return query(tree[pre].rs,tree[root].rs,i-1,x);
	}
	else
	{
		if (tree[tree[root].rs].size-tree[tree[pre].rs].size>=1) return query(tree[pre].rs,tree[root].rs,i-1,x)+(1<<i);
		else return query(tree[pre].ls,tree[root].ls,i-1,x);
	}
}
int main()
{
	//freopen("1.in","r",stdin);
	memset(f,0,sizeof(f));
	read(N),read(M);
	insert(rt[0],rt[1],60,0);
	for (LL a,i=2;i<=N+1;i++) read(a),sum[i]=sum[i-1]^a,insert(rt[i-1],rt[i],60,sum[i]); 
	len=(LL)sqrt(N+1);
	tot=(N+1)/len;
	if ((N+1)%len) tot++;
	for (LL i=1;i<=tot;i++)
	{
		b[i].l=(i-1)*len+1;
		b[i].r=i*len;
		f[i][b[i].l]=sum[b[i].l]^sum[b[i].l-1];
		for (LL j=b[i].l+1;j<=N+1;j++) f[i][j]=max(f[i][j-1],query(rt[b[i].l-1],rt[j],60,sum[j]));
	}
	b[tot].r=N+1;
	for (LL i=1;i<=N+1;i++) num[i]=(i-1)/len+1;
	while (M--)
	{
		o++;
		LL x,y;
		read(x),read(y);
		LL l=(LL)(1LL*x+1LL*lastans)%N+1LL,r=(LL)(1LL*y+1LL*lastans)%N+1LL;
		if (l>r) swap(l,r);
		l++,r++;
		lastans=0;
		if (num[l]==num[r])
		{
			for (LL i=l-1;i<=r;i++) lastans=max(lastans,query(rt[l-1],rt[r],60,sum[i]));
		}
		else
		{
			for (LL i=l-1;i<=b[num[l]].r;i++) lastans=max(lastans,query(rt[l-1],rt[r],60,sum[i]));
			lastans=max(lastans,f[num[l]+1][r]);
		}
		cout<<lastans<<endl;
	} 
	return 0;
}