http://www.lydsy.com/JudgeOnline/problem.php?id=2741
思路:我们先将a变成a的异或前缀，这样问题就变成了，在l-1到r区间内，找出i，j令a[i]^a[j]最大。
假如i是固定的，我们可以建一个可持久化trie，在l-1到r区间内贪心寻找最优，但是这题i和j都不是固定的，如果暴力枚举i，那时间复杂度最坏是m*n*logn。
因此我们考虑这样:将n个数字分块，预处理出数组f[i][j]，代表从第i块的开头作为左端点固定，j为右端点，这里面能产生的最优异或和，可以得到f[i][j]=max(f[i][j-1],query(root[start[i]-1],root[j],a[j]))，这样转移，就能在接近O(n)的时间复杂度内预处理出数组，这样，对于m个询问中的每个l,r，假如l属于块i,那么我们先让ans=f[i+1][r]，这样剩下我们只需要暴力解决l所属块i内的答案，这个求法就是上面说的固定点i，在root[l-1],root[r]区间内贪心查找，更新答案即可，还有这题，在强制在线的时候lastans+x和lastans+y可能会爆int。
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#define ll long long
int n,m,a[],b[],ch[][],sz,block_num,block_size,size[];
int f[][],root[];
int read(){
char ch=getchar();int t=,f=;
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int &k,int kk,int v,int dep){
k=++sz;
size[k]=size[kk]+;
if (dep==-) return;
ch[k][]=ch[kk][],ch[k][]=ch[kk][];
if (v&(<<dep)) insert(ch[k][],ch[kk][],v,dep-);
else insert(ch[k][],ch[kk][],v,dep-);
}
int query(int x,int y,int v){
int res=;
for (int i=;i>=;i--){
int t=((v&(<<i))>);
if (size[ch[y][t^]]-size[ch[x][t^]]>){
res|=(<<i);
y=ch[y][t^];
x=ch[x][t^];
}else{
y=ch[y][t];
x=ch[x][t];
}
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
block_size=(int)sqrt(n);
block_num=n/block_size+(n%block_size!=);
for (int i=;i<=n;i++) {scanf("%d",&a[i]);a[i]^=a[i-];}
int ans=;
for (int i=;i<=n;i++) insert(root[i],root[i-],a[i],);
for (int i=;i<=block_num;i++)
for (int j=(i-)*block_size+;j<=n;j++){
f[i][j]=std::max(f[i][j-],query(root[(i-)*block_size],root[j],a[j]));
if (i==) f[i][j]=std::max(f[i][j],a[j]);
}
while (m--){
int x,y;
scanf("%d%d",&x,&y);
x%=n;y%=n;
x=(x+(ans%n))%n+;
y=(y+(ans%n))%n+;
if (x>y) std::swap(x,y);
x--;
int num=x/block_size+(x%block_size!=);
ans=;
int l=num*block_size+;
if (l<=y) ans=f[num+][y];
l=std::min(l,y);
for (int j=x;j<l;j++)
ans=std::max(ans,query(root[x],root[y],a[j]));
printf("%d\n",ans);
}
}