题意是求 【a,b】 中 的最大字段异或和。 。
看了神牛题解才会的。
首先将 区间 转化成 前项和 中两个的异或值。
也就是 将 1- n 个数a[ ]，转化成 0-n 个数的数列b[ ]。
也就是
b[ r ] ^ a[ l ] = a[l+1] ^ a[l+2]^...^a[ r ]
b[2] ^ b[ 0 ] = a[1 ]^a[ 2 ]
在查询 【l,r】 转化成 b【】上的 【l-1, r】上的查询。（没处理好 ，一直在b【】 上 查询【l，r】 ，wa 成狗了。。）
于是此题问 就转化成了 在 在区间查询 两个点最大异或值。
对于一个点，查询是 【l,r】 是 复杂度 是 O(nlgm) : m 是 数列中最大值 lgm 是其位数。
所以求区间 任取两个点的最大异或值 ，lgn 应该没有解法。
于是参考神牛的解法， 分块，维护每一块的块头那个点 和其后边的每一个点 代表的区间中的最大值，
每一块块头部点 共有sqrt(n) 个，
f[ i ][j] = max(f[i][j-1],query(idx[i],j)); 第i块到 j的位置的最大值。
预处理的复杂度 O(nsqrt(n)*lgm)
查询时 暴力 第一块。 第二块的开头到 r 已经预处理出来了。
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <cstring>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <assert.h>
#include <queue>
#define REP(i,n) for(int i=0;i<n;i++)
#define TR(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define ALLL(x) x.begin(),x.end()
#define SORT(x) sort(ALLL(x))
#define CLEAR(x) memset(x,0,sizeof(x))
#define FILLL(x,c) memset(x,c,sizeof(x))
using namespace std;
const double eps = 1e-9;
#define LL long long
#define pb push_back
const int maxn = 31000;
const int T = 130;
int dp[100][maxn];
int a[maxn];
int b[maxn];
struct Node{
Node *s[2];
int sum;
}nodes[maxn*300];
Node *root[maxn],*null;
int C;
int n,m;
void init(){
C=0;
root[0] = null = &nodes[C++];
null->s[0] = null->s[1] = null;
null->sum = 0;
}
Node *insert(int v,int d,Node *root){
Node *rt = &nodes[C++];
rt->s[0] = root->s[0];
rt->s[1] = root->s[1];
rt->sum = root->sum+1;
if(d<0)return rt;
int p = (v>>d)&1;
rt->s[p] = insert(v,d-1,root->s[p]);
return rt;
}
int query(int v,int d,Node *rt1,Node *rt2){
if(d<0)return 0;
int p = (v>>d)&1;
if(rt2->s[p^1]->sum - rt1->s[p^1]->sum){
return (1<<d)+query(v,d-1,rt1->s[p^1],rt2->s[p^1]);
}
return query(v,d-1,rt1->s[p],rt2->s[p]);
}
const int K = 31;
void solve(){
init();
CLEAR(dp);
for(int i=0;i<=n;i++){
root[i+1] = insert(b[i],K,root[i]);
}
}
int get_ans(int l,int r){
int ans = 0;
l--;
int l_id = l/T+1;
int r_id = r/T+1;
if(r_id > l_id){
ans = dp[l_id+1][r];
}
for(int i=l;i<=min(r,(l_id+1)*T);i++){
ans = max(ans,query(b[i],K,root[l],root[r+1]));
}
return ans;
}
void solve1(){
int lastans = 0 ;
for(int i=1;i<=m;i++){
int l,r,x,y;
scanf("%d%d",&x,&y);
l = min(((x+lastans%n)%n)+1,((y+lastans%n)%n)+1);
r = max(((x+lastans%n)%n)+1,((y+lastans%n)%n)+1);
int ans = get_ans(l,r);
printf("%d\n",ans);
lastans = ans;
}
}
int main(){
scanf("%d%d",&n,&m);
CLEAR(b);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i] = b[i-1]^a[i];
}
solve();
for(int i=1;i<=n;i++){
int idx = i/T+1;
for(int j=1;j<=idx;j++){
int l_idx =(j-1)*T;
dp[j][i] = max(dp[j][i-1],query(b[i],K,root[l_idx],root[i+1]));
}
}
solve1();
return 0;
}