45pts tle求调

#include<bits/stdc++.h>
using namespace std;
#define N 50100
#define M 310
#define getchar getchar_unlocked
int L[M],R[M],pos[N];
int base,cnt;
int a[N],lsh[N],len;
vector<int> ton[N];
struct Node{int val,cnt;}pre[M][M];
int tim[N],cntv[N],ts; 
int n,q;
inline int read(){
    register int x=0;
    register char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x;
}
inline int get_count(int v,int l,int r){
    const vector<int>& vec=ton[v];
    auto it1=lower_bound(vec.begin(),vec.end(),l);
    auto it2=upper_bound(vec.begin(),vec.end(),r);
    return it2-it1;
}
inline void build(){
    base=sqrt(n*__lg(n))+1; 
    cnt=0;
    for(register int i=1;i<=n;i+=base){
        L[++cnt]=i;
        R[cnt]=min(L[cnt]+base-1,n);
        for(register int j=L[cnt];j<=R[cnt];j++)pos[j]=cnt;
    }
    for(register int j=1;j<=cnt;j++){
        for(register int i=j;i<=cnt;i++){
            ts++;
            int max_cnt=0,best_val=len+1;
            int l=L[j],r=R[i];
            for(register int k=l;k<=r;k++){
                int v=a[k];
                if(tim[v]!=ts){
                    tim[v]=ts;
                    cntv[v]=0;
                }
                cntv[v]++; 
                if(cntv[v]>max_cnt||(cntv[v]==max_cnt&&v<best_val)){
                    max_cnt=cntv[v];
                    best_val=v;
                }
            }
            pre[j][i].val=best_val;
            pre[j][i].cnt=max_cnt;
        }
    }
}
inline int query(int l,int r){
    register int p=pos[l],q=pos[r];
    if(p==q){
        ts++;
        int res_val=len+1,res_cnt=0;
        for(register int i=l;i<=r;i++){
            int v=a[i];
            if(tim[v]!=ts){
                tim[v]=ts;
                cntv[v]=0;
            }
            cntv[v]++;
            if(cntv[v]>res_cnt||(cntv[v]==res_cnt&&v<res_val)){
                res_cnt=cntv[v];
                res_val=v;
            }
        }
        return res_val;
    }
    int res_val=pre[p+1][q-1].val;
    int res_cnt=pre[p+1][q-1].cnt;
    ts++;
    vector<int> tmp;
    for(register int i=l;i<=R[p];i++){
        int v=a[i];
        if(tim[v]!=ts){
            tim[v]=ts;
            cntv[v]=0;
            tmp.push_back(v); 
        }
        cntv[v]++;
    }
    for(register int i=L[q];i<=r;i++){
        int v=a[i];
        if(tim[v]!=ts){
            tim[v]=ts;
            cntv[v]=0;
            tmp.push_back(v); 
        }
        cntv[v]++;
    }
    for(int v : tmp){
        int c=get_count(v,l,r);
        if(c>res_cnt||(c==res_cnt&&v<res_val)){
            res_cnt=c;
            res_val=v;
        }
    }
    return res_val;
}
inline void putnum(int x){
    if(x==0){putchar('0');return;}
    static char buf[10];
    int len=0;
    while(x){buf[len++]=x%10+'0';x/=10;}
    while(len--)putchar(buf[len]);
    putchar('\n');
}

int main(){
    n=read(),q=read();
    for(register int i=1;i<=n;i++)lsh[i]=a[i]=read();
    sort(lsh+1,lsh+1+n);
    len=unique(lsh+1,lsh+1+n)-lsh-1;
    for(register int i=1;i<=n;i++){
        a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;
        ton[a[i]].emplace_back(i);
    }
    build();
    int last_ans=0;
    while(q--){
        int l0=read(),r0=read();
        int l=((l0+last_ans-1)%n)+1;
        int r=((r0+last_ans-1)%n)+1;
        if(l>r)swap(l,r);
        last_ans=lsh[query(l,r)];
        putnum(last_ans);
    }
    return 0;
}