无妹子，吸氧全RE，自学分块的蒟蒻求助.jpg

#include<bits/stdc++.h>
using namespace std;
const int N=40005;
typedef long long ll;
ll a[N],b[N];
int L[N],R[N],t;
int pos[N];
int cnt[40][40][N],zs[40][40],zsc[40][40],mxm,mxn,p,q,lf,ri,f[N];
void check(int j) {
//  cout<<lf<<" "<<ri<<" "<<j<<": ";
    cnt[lf][ri][a[j]]++;
//      cout<<cnt[lf][ri][a[j]]<<endl;
    if (cnt[lf][ri][a[j]]>mxn || (cnt[lf][ri][a[j]]==mxn && a[j]<mxm)) {
        mxn=cnt[lf][ri][a[j]];
        mxm=a[j];
    }
}
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    t=(int)pow(n*1.0,1.0/3.0);
//  cout<<t<<endl;
    int T;
    if(t) T=n/t;
    for (int i=1; i<=n; i++) {
        scanf("%lld",&a[i]);
        //cout<<i<<":"<<a[i];
        //puts("");
        b[i]=a[i];
    }
    //return 0;
    sort(b+1,b+1+n);
    int cnti=unique(b+1,b+1+n)-b;
    for (int i=1; i<=n; i++) {
        a[i]=lower_bound(b+1,b+1+cnti,a[i])-b;
    }
    for (int i=1; i<=cnti; i++) f[a[i]]=b[i];
    for (int i=1; i<=t; i++) {
        L[i]=(i-1)*T+1;
        R[i]=i*T;
    }
    if (R[t]<n) {
        t++;
        L[t]=R[t-1]+1;
        R[t]=n;
    }
    for (int i=1; i<=t; i++) {
        for (int k=i; k<=t; k++) {
            for (int j=L[i]; j<=R[k]; j++) {
                cnt[i][k][a[j]]++;
            }
            for (int j=1; j<=cnti; j++) {
                if (cnt[i][k][j]>zsc[i][k] || cnt[i][k][j]==zsc[i][k] && j<zs[i][j]) {
                    zs[i][k]=j;
                    zsc[i][k]=cnt[i][k][j];
                }
            }
        }
    }
    int x=0;
    for (int i=1; i<=m; i++) {
        ll l0,r0;
        ll l,r;
        scanf("%lld %lld",&l0,&r0);
        l=(l0+x-1)%n+1;
        r=(r0+x-1)%n+1;
        if (l>r) swap(l,r);
        for (int j=1; j<=t; j++) if (l<=R[j]) {
                p=j;
                break;
            }
        for (int j=t; j>=1; j--) if (r>=L[j])   {
                q=j;
                break;
            }
        if (p+1<=q-1) {
            lf=l+1;
            ri=r-1;
        } else {
            lf=ri=0;
        }
        mxn=zsc[lf][ri],mxm=zs[lf][ri];
        if (p==q) {
            for (int j=l; j<=r; j++) check(j);
            for (int j=l; j<=r; j++) cnt[lf][ri][a[j]]--;
        } else {
            for (int j=l; j<=R[p]; j++) check(j);
            for (int j=L[q]; j<=r; j++) check(j);
            for (int j=l; j<=R[p]; j++) cnt[lf][ri][a[j]]--;
            for (int j=L[q]; j<=r; j++) cnt[lf][ri][a[j]]--;
        }
        printf("%d\n",f[mxm]);
        x=f[mxm];
    }
    return 0;
}