分块样例过0pts求调

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int a[40001];
int tmp[40001];
int she[40001];
int zf[40001];
int st[201],ed[201],bel[40001];
int f[201][201];
vector<int> dui[40001];
int last=0;
void hash_work(){
    for(int i=1;i<=n;i++)
        tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++){
        int k=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
        she[k]=a[i],a[i]=k;
    }
}
void pre(int step){
    for(int i=1;i<=n;i++)
        tmp[i]=0;
    int maxx__cnt=0,maxx__ans=0;
    for(int i=st[step];i<=n;i++){
        tmp[a[i]]++;
        if(tmp[a[i]]>maxx__cnt||(tmp[a[i]]==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
            maxx__cnt=tmp[a[i]],maxx__ans=a[i];
        f[step][bel[i]]=maxx__ans;
    }
}
int cnt_sum(int l,int r,int x){
    return upper_bound(dui[x].begin(),dui[x].end(),r)-lower_bound(dui[x].begin(),dui[x].end(),l);
}
int query(int l,int r){
    if(bel[r]-bel[l]<=2){
        int maxx__cnt=0,maxx__ans=0;
        for(int i=l;i<=r;i++){
            int k=cnt_sum(l,r,a[i]);
            if(k>maxx__cnt||(k==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
                maxx__cnt=k,maxx__ans=a[i];
        }
        return maxx__ans; 
    }
    else{
        int maxx__ans=f[bel[l]+1][bel[r]-1],maxx__cnt=cnt_sum(l,r,maxx__ans);
        for(int i=l;i<=ed[bel[l]];i++){
            int k=cnt_sum(l,r,a[i]);
            if(k>maxx__cnt||(k==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
                maxx__cnt=k,maxx__ans=a[i];
        }
        for(int i=st[bel[r]];i<=r;i++){
            int k=cnt_sum(l,r,a[i]);
            if(k>maxx__cnt||(k==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
                maxx__cnt=k,maxx__ans=a[i];
        }
        return maxx__ans; 
    }
}
signed main(){
    //freopen("P4168_1.in","r",stdin);
    memset(zf,0x3f,sizeof(zf));
    cin>>n>>m;q=sqrt(n);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    hash_work();
    for(int i=1;i<=n;i++)
        dui[a[i]].push_back(i),zf[a[i]]=min(zf[a[i]],i);
    for(int i=1;i<=q;i++)
        st[i]=n/q*(i-1)+1,ed[i]=n/q*i;ed[q]=n;
    for(int i=1;i<=q;i++)
        for(int j=st[i];j<=ed[i];j++)
            bel[j]=i;
    for(int i=1;i<=q;i++)
        pre(i);
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        l=(l+last-1)%n+1;
        r=(r+last-1)%n+1;
        if(l>r)swap(l,r);
        int ans=query(l,r);
        cout<<she[ans]<<'\n';last=she[ans];
    }
    return 0;
}