求助卡常

QAQ 85分T3点。（然后这三个点都是2.1几秒呜呜呜）

(复杂度上限在query里面)

#include <bits/stdc++.h>
#define ll long long
#define RE register
using namespace std;
int i,j,k,n,m;
void read(int &x){
    char c;x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
    do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;
}
void read(ll &x){
    char c;x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
    do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;
}
const int maxn=40000+10,maxN=200+10;
int N,a[maxn];
int mp[maxn],len=1;
void make(int &x){
    int L=1,R=len;
    while(R>=L){
        int Mid=L+R>>1;
        if(mp[Mid]==x){x=Mid;return;}
        if(mp[Mid]>x)R=Mid-1;
        else L=Mid+1;
    }
}
void in(){
    read(n);read(m);
    N=sqrt(n);
    for(int i=1;i<=n;i++)
        read(a[i]),mp[i]=a[i];
    sort(mp+1,mp+1+n);
    for(int i=2;i<=n;i++)
        if(mp[i]!=mp[i-1])
            mp[++len]=mp[i];
    for(int i=1;i<=n;i++)
        make(a[i]);
}
int Sum[maxN][maxN];
int B[maxn];
int block[maxn],Start[maxN],End[maxN];
void init_block(){
    for(int i=1;i<=n;i++){
        block[i]=(i-1)/N+1;
        if(block[i]!=block[i-1])
            Start[block[i]]=i;
        End[block[i]]=i;
    }
}
void init_Sum(){
    for(int i=1;i<=N;i++){
        memset(B,0,sizeof(B));
        int now=i,Max1=0,Max2=0;
        for(int j=Start[i];j<=n;j++){
            B[a[j]]++;
            if(B[a[j]]>Max1 || (B[a[j]]==Max1 && Max2>a[j])){
                Max1=B[a[j]];
                Max2=a[j];
            }
            if(j==End[now]){
                Sum[i][now]=Max2;
                ++now;
            }
        }
    }
}
int Num[maxn][maxN];
void init_Num(){
    int now=1;
    for(int i=1;i<=n;i++){
        B[a[i]]++;
        if(End[now]==i){
            for(int j=1;j<=n;j++)
                Num[j][now]=B[j];
            ++now;
        }
    }
}
void init(){
    init_block();
    init_Sum();
    init_Num();
}
int Q[4*maxN];
int find(int l,int r,int x){
    //cout<<"find:"<<l<<' '<<r<<' '<<x<<endl;
    int ans=0;
    if(block[l]==block[r]){
        for(int i=l;i<=r;i++)
            if(a[i]==x)
                ++ans;
    }else{
        for(int i=l;block[i]==block[l];i++)
            if(a[i]==x)
                ++ans;
        for(int i=r;block[i]==block[r];i--)
            if(a[i]==x)
                ++ans;
        //cout<<"FIND:"<<block[r]-1<<' '<<block[l]<<' '<<x<<' '<<Num[x][block[r]-1]<<endl;
        ans+=Num[x][block[r]-1]-Num[x][block[l]];
    }
    return ans;
}
int query(int l,int r){
    RE int len=0,i;
    if(block[l]==block[r]){
        for(i=l;i<=r;i++)
            Q[++len]=a[i];
    }else{
        for(i=l;block[i]==block[l];i++)
            Q[++len]=a[i];
        //cout<<"len:"<<len<<' ';
        for(i=r;block[i]==block[r];i--)
            Q[++len]=a[i];
        //cout<<len<<' ';
        if(block[r]-block[l]>1)
            Q[++len]=Sum[block[l]+1][block[r]-1];
        //cout<<len<<' ';
    }
    sort(Q+1,Q+1+len);
    //cout<<"len:"<<len<<' ';
    RE int L=1;
    for(i=2;i<=len;i++)
        if(Q[i]!=Q[i-1])
            Q[++L]=Q[i];
    len=L;
    //cout<<len<<endl;
    //cout<<l<<' '<<block[l]<<' '<<r<<' '<<block[r]<<endl;
    int Max1=0,Max2=0;
    for(i=1;i<=len;i++){
        int now=find(l,r,Q[i]);
        //cout<<i<<' '<<Q[i]<<' '<<now<<endl;
        if(now>Max1 || (Max1==now && Max2>Q[i])){
            Max1=now;
            Max2=Q[i];
        }
    }
    int ans=mp[Max2];
    printf("%d\n",ans);
    return ans;
}
void Query(){
    RE int lastans=0,l,r;
    for(int i=1;i<=m;i++){
        read(l);read(r);
        l=l+lastans-1;
        r=r+lastans-1;
        if(l>=n)l-=n;
        if(r>=n)r-=n;
        ++l;++r;
        if(l>r)swap(l,r);
        lastans=query(l,r)%n;
        //cout<<l<<' '<<r<<endl;
    }
}
int main() {
    in();
    init();
    Query();
    //cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
    return 0;
}