显然做个前缀和之后变成询问区间内两个数异或最大值。
一种暴力做法是建好可持久化trie后直接枚举其中一个数查询，复杂度O(nmlogv)。
观察到数据范围很微妙。考虑瞎分块。
设f[i][j]为第i个块中的数和第j个数的异或最大值。显然建一棵可持久化trie就可以以O(n√nlogv)的复杂度搞出来。
有了这个后考虑怎么查询。对于完整的块内的数，给f再搞一个st表就可以了。而其他部分暴力枚举每个数，在可持久化trie上查询即可。
常数巨大。块大小改成√nlogn后在darkbzoj上差10ms就T了，bzoj上自然过不了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define N 12010 #define BLOCK 120 #define u(x,p) x>>p&1^1 int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,a[N],f[BLOCK][N][14],root[N],L[BLOCK],R[BLOCK],pos[N],lg2[N],cnt=0,lastans,block; struct data{int ch[2],s; }tree[N<<5]; void ins(int &k,int x,int p) { tree[++cnt]=tree[k];k=cnt;tree[k].s++; if (p<0) return; ins(tree[k].ch[x>>p&1],x,p-1); } int query(int l,int r,int x,int p) { if (p<0) return 0; if (tree[tree[r].ch[u(x,p)]].s>tree[tree[l].ch[u(x,p)]].s) return query(tree[l].ch[u(x,p)],tree[r].ch[u(x,p)],x,p-1)+(1<<p); else query(tree[l].ch[x>>p&1],tree[r].ch[x>>p&1],x,p-1); } void build() { for (int i=1;i<=n;i++) { root[i]=root[i-1]; ins(root[i],a[i],30); } } int query(int i,int x,int y) { return max(f[i][x][lg2[y-x+1]],f[i][y-(1<<lg2[y-x+1])+1][lg2[y-x+1]]); } void divide() { lg2[1]=0; for (int i=2;i<=n;i++) { lg2[i]=lg2[i-1]; if ((2<<lg2[i])<=i) lg2[i]++; } block=sqrt(n*lg2[n]);block=min(max(block,1),n); for (int i=1;i<=n/block;i++) L[i]=(i-1)*block+1,R[i]=i*block; if (n%block) L[n/block+1]=(n/block)*block+1,R[n/block+1]=n,block=n/block+1; else block=n/block; for (int i=1;i<=block;i++) for (int j=L[i];j<=R[i];j++) pos[j]=i; for (int i=1;i<=n;i++) for (int j=1;j<=block;j++) f[j][i][0]=query(root[L[j]-1],root[R[j]],a[i],30); for (int i=1;i<=block;i++) for (int j=1;j<14;j++) for (int k=1;k<=n;k++) f[i][k][j]=max(f[i][k][j-1],f[i][min(n,k+(1<<j-1))][j-1]); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj2741.in","r",stdin); freopen("bzoj2741.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif n=read()+1,m=read(); for (int i=2;i<=n;i++) a[i]=a[i-1]^read(); build(); divide(); for (int i=1;i<=m;i++) { int x=((unsigned int)read()+lastans)%(n-1)+1,y=((unsigned int)read()+lastans)%(n-1)+1; if (x>y) swap(x,y);y++; lastans=0; for (int j=pos[x]+1;j<pos[y];j++) lastans=max(lastans,query(j,x,y)); if (pos[x]==pos[y]) { for (int j=x;j<=y;j++) lastans=max(lastans,query(root[x-1],root[y],a[j],30)); } else { for (int j=x;j<L[pos[x]+1];j++) lastans=max(lastans,query(root[x-1],root[y],a[j],30)); for (int j=y;j>R[pos[y]-1];j--) lastans=max(lastans,query(root[x-1],root[y],a[j],30)); } printf("%d\n",lastans); } return 0; }