分块不过样例求调教

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514],val[114514],before[114514];
int size,belong[114514],bl[114514],br[114514],bnum;
int sum[1145][40005];//Ç°i¸ö¿éÿ¸öÊýµÄ³öÏÖ´ÎÊý
int maxnum[1145][1145];//µÚi-j¸ö¿éµÄÖÚÊý 
int cnt[114514];
int tot;
void init()
{
    for(int i=1;i<=n;i++)
        val[i]=a[i];
    sort(val+1,val+n+1);
    tot=unique(val+1,val+n+1)-val-1;
    for(int i=1;i<=n;i++)
    {
        int k=lower_bound(val+1,val+tot+1,a[i])-val;
        a[i]=k;
        before[a[i]]=val[k];
    }
//  for(int i=1;i<=n;i++)
//      cout<<a[i]<<" "<<before[a[i]]<<endl;
}
void bld()
{
    size=sqrt(n);
    bnum=ceil(1.0*n/size);
    for(int i=1;i<=bnum;i++)
    {
        bl[i]=(i-1)*size+1;
        br[i]=i*size;
        for(int j=bl[i];j<=br[i];j++)
            belong[j]=i;
    }
    br[bnum]=n;
    for(int i=1;i<=bnum;i++)
    {
        for(int j=bl[i];j<=br[i];j++)
            ++sum[i][a[j]];
        for(int j=1;j<=tot;j++)
            sum[i][j]+=sum[i-1][j];
    }
    for(int i=1;i<=bnum;i++)
        for(int j=i;j<=bnum;j++)
        {
            int maxn=maxnum[i][j-1];
            for(int k=bl[j];k<=br[j];k++)
                if(sum[j][maxn]-sum[i-1][maxn]<sum[j][a[k]]-sum[i-1][a[k]]||
                sum[j][maxn]-sum[i-1][maxn]==sum[j][a[k]]-sum[i-1][a[k]]&&maxn>a[k])
                    maxn=a[k];
            maxnum[i][j]=maxn;
        }
//  for(int i=1;i<=bnum;i++)
//      for(int j=i;j<=bnum;j++)
//          cout<<i<<" "<<j<<" "<<maxnum[i][j]<<endl;
}
int bsum(int l,int r,int x)
{
    return sum[belong[r]][x]-sum[belong[l]-1][x];
}
int query(int l,int r)
{
    memset(cnt,0,sizeof cnt);
    if(belong[l]==belong[r])
    {
        int res=0,maxn=0;
        for(int i=l;i<=r;i++)
        {
            ++cnt[a[i]];
            if(maxn<cnt[a[i]]||maxn==cnt[a[i]]&&a[i]<res)
                maxn=cnt[a[i]],res=a[i];
        }
        return before[res];
    }
    int bmax=maxnum[belong[l]][belong[r]];
    int maxn=bsum(l,r,bmax),res=bmax;
    for(int i=l;i<=br[belong[l]];i++)
    {
        ++cnt[a[i]];
        if(cnt[a[i]]+bsum(l,r,a[i])>maxn)
            res=a[i],maxn=cnt[a[i]]+bsum(l,r,a[i]);
        if(cnt[a[i]]+bsum(l,r,a[i])==maxn&&a[i]<res)
            res=a[i];
    }
    for(int i=bl[belong[r]];i<=r;i++)
    {
//      cout<<a[i]<<" "<<cnt[a[i]]<<endl;
        ++cnt[a[i]];
        if(cnt[a[i]]+bsum(l,r,a[i])>maxn)
            res=a[i],maxn=cnt[a[i]]+bsum(l,r,a[i]);
        if(cnt[a[i]]+bsum(l,r,a[i])==maxn&&a[i]<res)
            res=a[i];
    }
    if(maxn<bsum(l,r,bmax))
        res=bmax;
    if(maxn==bsum(l,r,bmax)&&bmax<res)
        res=bmax;
    return before[res];
}
int ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    init();
    bld();
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        l=(l+ans-1)%n+1,r=(r+ans-1)%n+1;
        if(l>r)
            swap(l,r);
//      cout<<l<<" "<<r<<endl;
        ans=query(l,r);
        cout<<ans<<endl;
    }
}