求助，分块

算法进阶指南（李煜东）上的方法一，80 pts wa

#include<bits/stdc++.h>
using namespace std;
int n,m,pqr,len,lslen;
int a[40005],ls[40005];
int cnt[55][55][40005],zs[55][55];
int l[1005],r[1005],tot[40005];
int last;
int query(int x,int y)
{
    int p=tot[x],q=tot[y],ans=0;
    if(q-p==0)
    {
        for(int i=x;i<=y;++i)
        {
            cnt[0][0][a[i]]++;
            if(cnt[0][0][a[i]]>cnt[0][0][ans]||(cnt[0][0][a[i]]==cnt[0][0][ans]&&a[i]<ans))
            {
                ans=a[i];
            }
        }
        for(int i=x;i<=y;++i)
        {
            cnt[0][0][a[i]]--;
        }
    }
    else
    {
        ans=zs[p+1][q-1];
        for(int i=x;i<=r[p];++i)
        {
            cnt[p+1][q-1][a[i]]++;
            if(cnt[p+1][q-1][a[i]]>cnt[p+1][q-1][ans]||(cnt[p+1][q-1][a[i]]==cnt[p+1][q-1][ans]&&a[i]<ans))
            {
                ans=a[i];
            }
        }
        for(int i=l[q];i<=y;++i)
        {
            cnt[p+1][q-1][a[i]]++;
            if(cnt[p+1][q-1][a[i]]>cnt[p+1][q-1][ans]||(cnt[p+1][q-1][a[i]]==cnt[p+1][q-1][ans]&&a[i]<ans))
            {
                ans=a[i];
            }
        }
        for(int i=x;i<=r[p];++i)
        {
            cnt[p+1][q-1][a[i]]--;
        }
        for(int i=l[q];i<=y;++i)
        {
            cnt[p+1][q-1][a[i]]--;
        }
    }
    return ls[ans];
}
int main()
{
//  freopen("P4168_1.in","r",stdin);
//  freopen("1.out","w",stdout); 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        ls[i]=a[i];
    }
    sort(ls+1,ls+n+1);
    lslen=unique(ls+1,ls+n+1)-ls;
    for(int i=1;i<=n;++i)
    {
        int ch=lower_bound(ls+1,ls+lslen+1,a[i])-ls;
        a[i]=ch;
    }
    for(;len*len*len<=n;++len);
    len--;
    pqr=n/len;
    for(int i=1;i<=len;++i)
    {
        l[i]=(i-1)*pqr+1;
        r[i]=i*pqr;
    }
    if(len*pqr!=n)
    {
        l[len+1]=len*pqr+1;
        r[len+1]=n;
        len++;
    }
    for(int i=1;i<=len;++i)
    {
        for(int j=l[i];j<=r[i];++j)
        {
            tot[j]=i;
        }
    }
    for(int i=1;i<=len;++i)
    {
        for(int j=i;j<=len;++j)
        {
            for(int k=l[i];k<=r[j];++k)
            {
                cnt[i][j][a[k]]++;
            }
            int tot=0;
            for(int k=1;k<=lslen;++k)
            {
                if(cnt[i][j][k]>tot)
                {
                    tot=cnt[i][j][k];
                    zs[i][j]=k;
                }
            }
        }
    }
    while(m--)
    {
        int l0,r0;
        scanf("%d%d",&l0,&r0);
        int p=(l0+last-1)%n+1,q=(r0+last-1)%n+1;
        if(p>q)
        swap(p,q);
        last=query(p,q);
        printf("%d\n",last);
    }
}