75pts 求解

#include<bits/stdc++.h>
using namespace std;
int rt,st,ed,ll,rr,x,y,n,m,t,k,S,s,tt,ans1,ans2,ans,zong[1001][1001],a[4000001],b[4000001],l[4000001],r[4000001],sum[4000001],f[1001][1001],pr[4000001];
bool ff[10000001];
inline int js(int x,int y)
{
    if(y-x<2*S)
    {
        ans2=0x3f3f3f3f,ans1=-0x3f3f3f3f;
        for(int i=x; i<=y; ++i)
            if(!ff[a[i]]) ff[a[i]]=true,sum[a[i]]=1;
            else ++sum[a[i]];
        for(int i=x; i<=y; ++i)
            if(ff[a[i]])
            {
                if((sum[a[i]]>ans1)||(sum[a[i]]==ans1&&a[i]<ans2)) ans1=sum[a[i]],ans2=a[i];
                ff[a[i]]=false;
            }
    }
    else
    {
        ll=x/S+1,rr=y/S+1;
        if(x==l[ll]) --ll;
        if(y==r[rr]) ++rr;
        ans2=zong[ll+1][rr-1],ans1=f[ans2][rr-1]-f[ans2][ll],ed=r[ll],st=l[rr];
        for(int i=x; i<=ed; ++i)
            if(!ff[a[i]]) ff[a[i]]=true,sum[a[i]]=1;
            else ++sum[a[i]];
        for(int i=st; i<=y; ++i)
            if(!ff[a[i]]) ff[a[i]]=true,sum[a[i]]=1;
            else ++sum[a[i]];
        for(int i=x; i<=ed; ++i)
            if(ff[a[i]])
            {
                int lcq=f[a[i]][rr-1]-f[a[i]][ll]+sum[a[i]];
                if((lcq>ans1)||(lcq==ans1&&a[i]<ans2)) ans1=lcq,ans2=a[i];
                ff[a[i]]=false;
            }
        for(int i=st; i<=y; ++i)
            if(ff[a[i]])
            {
                int lcq=f[a[i]][rr-1]-f[a[i]][ll]+sum[a[i]];
                if((lcq>ans1)||(lcq==ans1&&a[i]<ans2)) ans1=lcq,ans2=a[i];
                ff[a[i]]=false;
            }
    }
    return b[ans2];
}
int main()
{
    scanf("%d%d",&n,&m),S=sqrt(n);
    for(int i=0; i<n; ++i) scanf("%d",&a[i]),b[i]=a[i];
    sort(b,b+n),t=unique(b,b+n)-b;
    for(int i=0; i<n; ++i) a[i]=lower_bound(b,b+t,a[i])-b;
    for(int i=0; i<n; ++i) if(i%S==0) r[tt]=i-1,l[++tt]=i;
    r[tt]=n-1,l[tt+1]=r[tt+1]=n;
    for(int i=1; i<=tt; ++i)
    {
        for(int j=l[i]; j<n; ++j) sum[a[j]]=0;
        k=l[i],ans1=-0x3f3f3f3f,ans2=0x3f3f3f3f;
        for(int j=i; j<=tt; ++j)
        {
            for(; k<=r[j]; ++k)
            {
                ++sum[a[k]],rt=sum[a[k]];
                if((rt>ans1)||(rt==ans1&&a[k]<ans2))  ans1=rt,ans2=a[k];
            }
            zong[i][j]=ans2;
        }
    }
    memset(sum,0,sizeof(sum));
    for(int i=1; i<=tt; ++i)
    {
        for(int j=0; j<t; ++j) f[j][i]=f[j][i-1];
        for(int j=l[i]; j<=r[i]; ++j) f[a[j]][i]=++sum[a[j]];
    }
    while(m--)
    {
        scanf("%d%d",&x,&y),x=(x+ans-1)%n,y=(y+ans-1)%n;
        if(x>y) swap(x,y);
        ans=js(x,y),printf("%d\n",ans);
    }
    return 0;
}