85pts WA 2-5求调悬关

#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define dn(i,l,r) for(int i=(l);i>=(r);--i)
const int N=40005;
const int K=800;
int len,bel[N],lk[K],rk[K],out[N],m,lst=0,s[K][N],mxt[K][K],n,q;
int mp[N],tim[K][K],a[N],li[N],l,r;
bool vs[N];
struct fk{
    inline void init(){
        len=sqrt(n);
        up(i,1,n) bel[i]=(i-1)/len+1;
        up(i,1,n) rk[bel[i]]=i;
        dn(i,n,1) lk[bel[i]]=i;
        up(i,1,len){
            up(j,1,m) s[i][j]=s[i-1][j];
            up(j,lk[i],rk[i]){
                ++s[i][a[j]];
            }
        }
        up(i,1,len){
            int mxn=0;
            fill(mp+1,mp+m+1,0); 
            up(k,lk[i],n){
                ++mp[a[k]];
                if(mp[a[k]]>mp[mxn]){
                    mxn=a[k];
                }else if(mp[a[k]]==mp[mxn]){
                    if(a[k]<mxn){
                        mxn=a[k];
                    }
                }
                mxt[i][bel[k]]=mxn;
                tim[i][bel[k]]=mp[mxn];
            }
        }
//      up(i,1,len){
//          up(j,i,len){
////                cout<<"众数:"<<i<<' '<<j<<' '<<mxt[i][j]<<'\n';
//          }
//      }
        return;
    }
    inline int query(int l,int r){
        int ans=0;mp[0]=0;
        if(bel[r]-bel[l]<=2){
            up(i,l,r) mp[a[i]]=0;
            up(i,l,r){
                ++mp[a[i]];
                if((mp[a[i]]>mp[ans])||((mp[a[i]]==mp[ans])&&(a[i]<ans))){
                    ans=a[i];
                }
            }
            return out[ans];
        }
        up(i,l,rk[bel[l]]) mp[a[i]]=0,vs[a[i]]=0;
        dn(i,r,lk[bel[r]]) mp[a[i]]=0,vs[a[i]]=0;
        mp[mxt[bel[l]+1][bel[r]-1]]=0;vs[mxt[bel[l]+1][bel[r]-1]]=0;
        mp[mxt[bel[l]+1][bel[r]-1]]=0;
        up(i,l,rk[bel[l]]) mp[a[i]]++;
        dn(i,r,lk[bel[r]]) mp[a[i]]++;
        mp[mxt[bel[l]+1][bel[r]-1]]+=tim[bel[l]+1][bel[r]-1];vs[mxt[bel[l]+1][bel[r]-1]]=1;
        up(i,l,rk[bel[l]]){
            if(!vs[a[i]]){
                mp[a[i]]+=s[bel[r]-1][a[i]]-s[bel[l]][a[i]];vs[a[i]]=1;
            }
        }
        dn(i,r,lk[bel[r]]){
            if(!vs[a[i]]){
                mp[a[i]]+=s[bel[r]-1][a[i]]-s[bel[l]][a[i]];vs[a[i]]=1;
            }
        }
        up(i,l,rk[bel[l]]){
            if(mp[a[i]]>mp[ans]){
                ans=a[i];
            }else if((mp[a[i]]==mp[ans])&&(a[i]<ans)){
                ans=a[i];
            }
        }
        dn(i,r,lk[bel[r]]){
            if(mp[a[i]]>mp[ans]){
                ans=a[i];
            }else if((mp[a[i]]==mp[ans])&&(a[i]<ans)){
                ans=a[i];
            }
        }
        if((mp[mxt[bel[l]+1][bel[r]-1]]>mp[ans])||((mp[mxt[bel[l]+1][bel[r]-1]]==mp[ans])&&(mxt[bel[l]+1][bel[r]-1]<ans))){
            ans=mxt[bel[l]+1][bel[r]-1];
        }
        return out[ans];
    }
}bit;
int main(){
//  freopen("P4168_1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>q;
    up(i,1,n){
        cin>>a[i];li[i]=a[i];
    }
    sort(li+1,li+n+1);
    m=unique(li+1,li+n+1)-li-1;
    up(i,1,m) out[i]=li[i];
    up(i,1,n) a[i]=lower_bound(li+1,li+m+1,a[i])-li;
    bit.init();
    up(i,1,q){
        cin>>l>>r;
        l=((l+lst-1)%n)+1;r=((r+lst-1)%n)+1;
        if(l>r) swap(l,r);
        lst=bit.query(l,r);
        cout<<lst<<'\n';
    }
    return 0;
}
//tomxi