区间上的异或问题，不难想到用可持久化线段树解决
求l到r的最大异或和，暴力自然是枚举左右端点，但显然时间不允许
用分块的方法处理
枚举右端点，处理出每个右端点到每个快左端点的区间最大异或和
询问时暴力枚举不在块内的点作为左端点即可
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,tot,num,ans; 7 int rt[12005]; 8 int vl[12005]; 9 int tr[400005][2]; 10 int siz[400005]; 11 int f[155][12005]; 12 void insert(int fr,int tim,int s){ 13 int now=rt[tim]=++tot; 14 for(int i=30;i>=0;i--){ 15 tr[now][!((s>>i)&1)]=tr[fr][!((s>>i)&1)]; 16 tr[now][(s>>i)&1]=++tot; 17 now=tr[now][(s>>i)&1]; 18 fr=tr[fr][(s>>i)&1]; 19 siz[now]=siz[fr]+1; 20 } 21 } 22 int query(int s,int fr,int now){ 23 int ret=0; 24 for(int i=30;i>=0;i--){ 25 if(siz[tr[now][!((s>>i)&1)]]>siz[tr[fr][!((s>>i)&1)]]){ 26 ret|=(1<<i); 27 now=tr[now][!((s>>i)&1)]; 28 fr=tr[fr][!((s>>i)&1)]; 29 }else{ 30 now=tr[now][(s>>i)&1]; 31 fr=tr[fr][(s>>i)&1]; 32 } 33 } 34 return ret; 35 } 36 void getprt(){ 37 for(int i=1;i<=(n/num)+1;i++){ 38 for(int j=(i-1)*num+1;j<=n;j++){ 39 int l=(i-1)*num-1;int r=rt[j-1]; 40 l=(l<0)?0:rt[l]; 41 f[i][j]=max(f[i][j-1],query(vl[j],l,r)); 42 } 43 } 44 } 45 int main(){ 46 scanf("%d%d",&n,&m); 47 num=sqrt(n+1)+1; 48 insert(0,0,0); 49 for(int i=1;i<=n;i++){ 50 scanf("%d",&vl[i]); 51 vl[i]^=vl[i-1]; 52 insert(rt[i-1],i,vl[i]); 53 } 54 getprt(); 55 for(int i=1;i<=m;i++){ 56 int l,r; 57 scanf("%d%d",&l,&r); 58 l=((long long)l+ans)%n+1;r=((long long)r+ans)%n+1; 59 if(l>r)swap(l,r); 60 int p=l/num+2; 61 ans=f[p][r]; 62 for(int j=l;j<=min((p-1)*num,r);j++){ 63 ans=max(ans,query(vl[j-1],rt[l-1],rt[r])); 64 } 65 printf("%d ",ans); 66 } 67 return 0; 68 }