WA0pts求助

RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=40007;
const int M=227;
int n,m,len,tot=0,a[N],sum[M][N],L[M],R[M],pos[N],T[N],b[N],tmp[N],last=0;
struct node{int cnt,id;}f[M][M];
int vis[N]; 
inline int query(int ql,int qr){
    int ans=0;
    if(pos[qr]-pos[ql]<=2){
        for(int i=ql;i<=qr;i++)T[b[i]]=0;
        for(int i=ql;i<=qr;i++){
            T[b[i]]++;
            if(T[b[i]]>T[ans])ans=b[i];
            else if(T[b[i]]==T[ans])ans=min(ans,b[i]);
        } 
        return a[ans];
    }
    ans=f[pos[ql]+1][pos[qr]-1].id;
    T[ans]=0,vis[ans]=0;
    for(int i=ql;i<=R[pos[ql]];i++)T[b[i]]=0,vis[b[i]]=0;
    for(int i=L[pos[qr]];i<=qr;i++)T[b[i]]=0,vis[b[i]]=0;
    for(int i=ql;i<=R[pos[ql]];i++)T[b[i]]++;
    for(int i=L[pos[qr]];i<=qr;i++)T[b[i]]++;
    int mx=0,id=0;
    for(int i=ql;i<=R[pos[ql]];i++){
        if(!vis[b[i]]){
            vis[b[i]]=1;
            int res=sum[pos[qr]-1][b[i]]-sum[pos[ql]][b[i]]+T[b[i]];
            if(res>mx){
                mx=res;
                id=b[i];
            }else if(res==mx)id=min(id,b[i]);
        }
    }
    for(int i=L[pos[qr]];i<=qr;i++){
        if(!vis[b[i]]){
            vis[b[i]]=1;
            int res=sum[pos[qr]-1][b[i]]-sum[pos[ql]][b[i]]+T[b[i]];
            if(res>mx){
                mx=res;
                id=b[i];
            }else if(res==mx)id=min(id,b[i]);
        }
    }
    int X=T[ans]+f[pos[ql]+1][pos[qr]-1].cnt;
    if(mx>X)ans=id;
    else if(mx==X)ans=min(ans,id);
    return a[ans];
}
signed main(){
    cin>>n>>m;
    len=sqrt(n);
    tot=(n-1)/len+1;
    for(int i=1;i<=n;i++)cin>>a[i],pos[i]=(i-1)/len+1,b[i]=a[i],tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);
    int GG=unique(tmp+1,tmp+n+1)-(tmp+1);
    for(int i=1;i<=n;i++)b[i]=lower_bound(tmp+1,tmp+GG+1,b[i])-tmp;
//  for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<"\n";
    for(int i=1;i<=tot;i++)L[i]=R[i-1]+1,R[i]=i*len;
    R[tot]=n;
    for(int i=1;i<=tot;i++){
        memset(T,0,sizeof(T));node res={0,0};
        for(int j=i;j<=tot;j++){
            for(int k=L[j];k<=R[j];k++){
                T[b[k]]++;
                if(T[b[k]]>res.cnt){
                    res.cnt=T[b[k]];
                    res.id=b[k];
                }else if(T[b[k]]==res.cnt)res.id=min(b[k],res.id);
            }
            f[i][j]=res;
        }
    }
    for(int i=1;i<=tot;i++){
        for(int j=1;j<=n;j++)sum[i][b[j]]=sum[i-1][b[j]];
        for(int j=L[i];j<=R[i];j++)sum[i][b[j]]++;
    }
    memset(T,0,sizeof(T));
    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);
        last=query(l,r);
        cout<<last<<"\n";
    }
}