解题思路
首先求出前缀异或和，那么问题就转化成了区间内选两个数使得其异或和最大。数据范围不是很大考虑分块，设\(f[x][i]\)表示第\(x\)块开头到\(i\)这个位置与\(a[i]\)异或得到的最大的数，而对\(f\)求前缀\(max\)就可以得出每一块的开头到后面任意一点的区间内异或最大。而求\(f\)的过程实际是从区间内取一个数和给定数异或和最大，那么这个可以用\(0/1\) \(Trie\)来做，就可以造一棵可持久化\(Trie\)。询问时整块直接调用\(f\)，前面的小块直接用可持久化\(Trie\)求解，时间复杂度\(O(n\sqrt(n) logn)\)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=12005;
const int M=N*60;
typedef long long LL;
template<class T> void rd(T &x){
x=0; char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
inline int max(int x,int y) {return x>y?x:y;}
int n,m,siz,num,rt[N],tot,bl[N],l[N],r[N];
int a[N],f[205][N],lstans,zz[N];
struct Trie{
int ch[M][2],sum[M];
void insert(int pre,int &x,int now,int d){
x=++tot; sum[x]=sum[pre]+1; if(!d) return ;
ch[x][0]=ch[pre][0]; ch[x][1]=ch[pre][1];
if(now&(1<<(d-1))) insert(ch[pre][1],ch[x][1],now,d-1);
else insert(ch[pre][0],ch[x][0],now,d-1);
}
int query(int u,int v,int now,int d){
if(!d) return 0;
if(now&(1<<(d-1))) {
if(sum[ch[u][0]]-sum[ch[v][0]]!=0)
return (query(ch[u][0],ch[v][0],now,d-1))|(1<<(d-1));
else return query(ch[u][1],ch[v][1],now,d-1);
}
else {
if(sum[ch[u][1]]-sum[ch[v][1]]!=0)
return (query(ch[u][1],ch[v][1],now,d-1)|(1<<(d-1)));
else return query(ch[u][0],ch[v][0],now,d-1);
}
}
}tree;
inline void prework(){
for(int i=1;i<=num;++i)
for(int j=l[i]+1;j<=n;++j)
f[i][j]=tree.query(rt[j],rt[l[i]-1],a[j],31);
// for(int i=1;i<=num;i++)
// for(int j=l[i]+1;j<=n;j++)
// printf("f[%d][%d]=%lld\n",i,j,f[i][j]);
for(int i=1;i<=num;++i)
for(int j=l[i]+1;j<=n;++j)
f[i][j]=max(f[i][j],f[i][j-1]);
}
inline int ask(int x,int y){
int ret=0;
if(bl[x]==bl[y]){
for(int i=x;i<y;++i)
ret=max(ret,tree.query(rt[y],rt[max(0,x-1)],a[i],31));
return ret;
}
ret=f[bl[x]+1][y];
for(int i=x;i<=r[bl[x]];++i)
ret=max(ret,tree.query(rt[y],rt[max(0,x-1)],a[i],31));
return ret;
}
signed main(){
rd(n),rd(m); siz=sqrt(n);
num=n/siz; if(n%siz) num++;
for(int i=1;i<=n;++i){
rd(a[i]); bl[i]=(i-1)/siz+1; a[i]^=a[i-1];
tree.insert(rt[i-1],rt[i],a[i],31);
}
for(int i=1;i<=num;++i) l[i]=(i-1)*siz+1,r[i]=i*siz;
r[num]=n; prework(); int L,R;
while(m--){
rd(L); rd(R);
L=((LL)lstans+L)%n+1,R=((LL)lstans+R)%n+1;
if(L>R) swap(L,R); lstans=ask(L-1,R);
printf("%d\n",lstans);
}
return 0;
}