分块求调

#include<bits/stdc++.h>
using namespace std;
int n,m,a[40005],b[40005],tot,x,t,len,pos[45],l[45],r[45],c[45][45][40005],d[45][45][2],now[2],l0,r0,l1,r1,tt,book[40005];
int ask(int l1,int r1){
    int p=pos[l1],q=pos[r1];
    if(p+1<=q-1){
        now[0]=d[p+1][q-1][0];
        now[1]=d[p+1][q-1][1];
        for(int i=l1;i<=r[p];i++){
            c[p+1][q-1][a[i]]++;
            if(c[p+1][q-1][a[i]]>now[0]||c[p+1][q-1][a[i]]==now[0]&&a[i]<now[1]){
                now[0]=c[p+1][q-1][a[i]];
                now[1]=a[i];
            }
        }
        for(int i=l[q];i<=r1;i++){
            c[p+1][q-1][a[i]]++;
            if(c[p+1][q-1][a[i]]>now[0]||c[p+1][q-1][a[i]]==now[0]&&a[i]<now[1]){
                now[0]=c[p+1][q-1][a[i]];
                now[1]=a[i];
            }
        }
        for(int i=l1;i<=r[p];i++){
            c[p+1][q-1][a[i]]--;
        }
        for(int i=l[q];i<=r1;i++){
            c[p+1][q-1][a[i]]--;
        }
        return now[1];
    }
    else{
        memset(book,0,sizeof(book));
        now[1]=0;now[0]=0;
        for(int i=l1;i<=r1;i++){
            book[a[i]]++;
            if(book[a[i]]>now[0]||book[a[i]]==now[0]&&a[i]<now[1]){
                now[0]=book[a[i]];
                now[1]=a[i];
            }
        }
        return now[1];
    }
}
bool cmp(int x,int y) {
    return x<y;
}
int main(){
    freopen("1972.in","r",stdin);
    freopen("1972.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        b[i]=a[i];
    }
    sort(b+1,b+1+n,cmp);
    tot=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
    }
    t=(int)pow((double) n,(double) 1/3);
    len=t*t;
    for(int i=1;i<=t;i++){
        l[i]=(i-1)*len+1;
        r[i]=i*len;
    }
    if(r[t]<n){
        t++;
        l[t]=r[t-1]+1;
        r[t]=n;
    }
    for(int i=1;i<=t;i++){
        for (int j=l[i];j<=r[i];j++) {
            pos[j]=i;
        }
    }
    for(int i=1;i<=t;i++){
        for(int j=i;j<=t;j++){
            for(int k=l[i];k<=r[j];k++){
                c[i][j][a[k]]++;
                if(c[i][j][a[k]]>d[i][j][0]||c[i][j][a[k]]==d[i][j][0]&&a[i]<d[i][j][1]){
                    d[i][j][0]=c[i][j][a[k]];
                    d[i][j][1]=a[i];
                }
            }
        }
    }
    for(int i=1;i<=m;i++){
        cin>>l0>>r0;
        l1=((l0+x-1)%n)+1;
        r1=((r0+x-1)%n)+1;
        if (l1>r1) swap(l1,r1); 
        if (l1<1) l1=1;
        if (r1>n) r1=n; 
        x=ask(l1,r1);
        x=b[x];
        cout<<x<<endl;
    } 
    return 0;
}