BZOJ2741: 【FOTILE模拟赛】L

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=2e4+10;
const double eps=1e-8;
#define ll long long
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}
typedef struct node{
    int c[2],sum;
}node;
node d[41*MAXN];
int rt[MAXN],cnt,n,m,sz,p[MAXN];
ll a[MAXN],sum[MAXN],ans[201][201];
void insert(int x,ll k){
    bool flag;
    dec(i,40,0){
        flag=k&(1LL<<i);
        int t=++cnt;d[t]=d[d[x].c[flag]];d[t].sum++;d[x].c[flag]=t;x=t;
    }
}
ll querty(int x,int y,ll k){
    if(x>=y)return 0;
    bool flag;
    ll res=0;
    dec(i,40,0){
        flag=k&(1LL<<i);
        if(flag){
            if(d[d[y].c[0]].sum-d[d[x].c[0]].sum)y=d[y].c[0],x=d[x].c[0];
            else x=d[x].c[1],y=d[y].c[1],res+=(1LL<<i);
        }
        else{
            if(d[d[y].c[1]].sum-d[d[x].c[1]].sum)x=d[x].c[1],y=d[y].c[1],res+=(1LL<<i);
            else x=d[x].c[0],y=d[y].c[0];
        }
    }
    return (res^k);
    //return (id[y]^k);
}
ll solve(int x,int y){
    //cout<<x<<" "<<y<<" "<<p[x]<<" "<<p[y]<<endl;
    if(p[y]-p[x]<=1){
        ll ans1=a[x];
        inc(i,x+1,y){
            //cout<<sum[i]<<"===="<<endl;
            ans1=max(max(ans1,querty(rt[x-2],rt[i-1],sum[i])),sum[i]^sum[i-1]);
        }
        return ans1;
    }
    ll ans2=ans[p[x]+1][p[y]-1];
    //cout<<ans2<<endl;
    inc(i,x,p[x]*sz)ans2=max(max(ans2,querty(rt[i],rt[y],sum[i-1])),sum[i]^sum[i-1]);
    //cout<<ans2<<endl;
    inc(i,(p[y]-1)*sz+1,y)ans2=max(max(ans2,querty(rt[x-2],rt[i-1],sum[i])),sum[i]^sum[i-1]);
   // cout<<ans2<<endl;
    return ans2;
}
int main(){
    n=read();m=read();sz=sqrt(n);
    inc(i,1,n)a[i]=read(),sum[i]=a[i]^sum[i-1];
    rt[0]=++cnt;insert(rt[0],0);
    inc(i,1,n){rt[i]=++cnt;d[rt[i]]=d[rt[i-1]];insert(rt[i],sum[i]);}
    inc(i,1,n)p[i]=(i-1)/sz+1;
   // cout<<sz<<endl;
    inc(i,1,p[n]){
        int t=(i-1)*sz+1;
        ll ans2=a[t];
        inc(k,(i-1)*sz+2,min(n,i*sz))ans2=max(max(ans2,querty(rt[t-2],rt[k-1],sum[k])),sum[k]^sum[k-1]);
        ans[i][i]=ans2;
        inc(j,i+1,p[n]){
            ll ans1=a[t];
            inc(k,(j-1)*sz+1,min(n,j*sz))ans1=max(max(ans1,querty(rt[t-2],rt[k-1],sum[k])),sum[k]^sum[k-1]);
            ans[i][j]=max(ans[i][j-1],ans1);
            //cout<<i<<" "<<j<<" "<<ans[i][j]<<endl;
        }
    }
    ll res=0;int l,r,x,y;
    while(m--){
        x=read();y=read();
        l=min((x+res)%n+1,(y+res)%n+1);r=max((x+res)%n+1,(y+res)%n+1);
        res=solve(l,r);
        printf("%lld\n",res);
    }
    return 0;
}