捞
题名：蒲公英。
题意：求区间众数，$n \le 40000$

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int Maxn=4e4+5;
int n,m,t;//t为块长
int a[Maxn],b[Maxn],nn;
int l[205],r[205],k[Maxn],kuai;
int sum[205][40000],p[205][205];//sum[i][j]是1到i块j的个数,p[i][j]是从i到j块的众数
int l0,r0,ql,qr,last;
int ans[Maxn];

void init()
{
    t=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        k[i]=(i-1)/t+1;
        if(k[i]!=k[i-1])
        {
            l[++kuai]=i;
            r[kuai-1]=i-1;
        }
    }
    r[kuai]=n;
    for(int i=1;i<=n;i++)
    {
        if(k[i]!=k[i-1])
            for(int j=1;j<=n;j++)
                sum[k[i]][j]=sum[k[i]-1][j];
        sum[k[i]][a[i]]++;
    }
    for(int i=1;i<=k[n];i++)
    {
        for(int j=i;j<=k[n];j++)
        {
            p[i][j]=p[i][j-1];
            for(int k=l[j];k<=r[j];k++)
            {
                int tak=sum[a[k]][j]-sum[a[k]][i-1];
                int tp=sum[p[i][j]][j]-sum[p[i][j]][i-1];
                if(tak<tp||(tak==tp&&a[k]<p[i][j])) p[i][j]=a[k];
            }
        }
    }
}
#define zuo for(int i=ql;i<=r[k[ql]];i++)
#define you for(int i=l[k[qr]];i<=qr;i++)
#define zhong for(int i=ql;i<=qr;i++)
int query(int ql,int qr)
{
    int res=0;
    if(k[qr]-k[ql]<=1)
    {
        zhong
        {
            ans[a[i]]++;
            if(ans[a[i]]>ans[res]||(ans[a[i]]==ans[res]&&a[i]<res)) res=a[i];
        }
        zhong ans[a[i]]=0;
        return res;
    }
    zuo if(!ans[a[i]]) ans[a[i]]=sum[k[qr]-1][a[i]]-sum[k[ql]][a[i]];
    you if(!ans[a[i]]) ans[a[i]]=sum[k[qr]-1][a[i]]-sum[k[ql]][a[i]];
    zuo if(++ans[a[i]]>ans[res]||(ans[a[i]]==ans[res]&&a[i]<res)) res=a[i];
    you if(++ans[a[i]]>ans[res]||(ans[a[i]]==ans[res]&&a[i]<res)) res=a[i];
    int mid=p[k[ql]+1][k[qr]-1];
    int timemid=sum[k[qr]-1][mid]-sum[k[ql]][mid];
    zuo timemid+=(a[i]==mid);
    you timemid+=(a[i]==mid);
    if(timemid>ans[res]||(timemid==ans[res]&&mid<res)) res=mid;
    zuo ans[a[i]]=0;
    you ans[a[i]]=0;
    return res;
}

signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    nn=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+nn,a[i])-b;
    init();
    while(m--)
    {
        scanf("%d%d",&l0,&r0);
        int ql=(l0+last-1)%n+1;
        int qr=(r0+last-1)%n+1;
        if(ql>qr) swap(ql,qr);
        last=query(ql,qr);
        printf("%d\n",b[last]);
    }
    return 0;
}