记录编号	616785	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	蒲公英	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	11.498 s
提交时间	2026-06-30 17:36:34	内存使用	7.04 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=40010;
const int M=50010;
const int B=210;

int n,m,last,tot,bcnt;
int a[N],c[N],val[N],id[N],L[B],R[B],p[B][B],s[B][N];
int lik[N];                    
vector<int> idx[N];             
void init()
{
    vector<int> v;
    for(int i=1;i<=n;++i)
        v.push_back(a[i]);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    tot=v.size();
    for(int i=1;i<=n;++i)
    {
        c[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
        val[c[i]]=a[i];
        idx[c[i]].push_back(i);
        lik[i]=idx[c[i]].size()-1;
    }
    bcnt=(n-1)/B+1;
    for(int i=1;i<=bcnt;++i)
    {
        L[i]=(i-1)*B+1;
        R[i]=min(i*B,n);
        for(int j=L[i];j<=R[i];j++)
            id[j]=i;
    }
    for(int i=1;i<=bcnt;++i)
    {
        for(int j=1;j<=tot;j++)
            s[i][j]=s[i-1][j];
        for(int j=L[i];j<=R[i];j++)
            s[i][c[j]]++;
    }
    for(int i=1;i<=bcnt;++i)
    {
        int cnt[N]={0};
        int mx=0,res=0;
        for(int j=i;j<=bcnt;j++)
        {
            for(int k=L[j];k<=R[j];k++)
            {
                int x=c[k];
                cnt[x]++;
                if(cnt[x]>mx||(cnt[x]==mx&&x<res))
                {
                    mx=cnt[x];
                    res=x;
                }
            }
            p[i][j]=res;
        }
    }
}

int get_cnt(int l,int r,int x)
{
    if(idx[x].empty()) return 0;
    return upper_bound(idx[x].begin(),idx[x].end(),r)-
           lower_bound(idx[x].begin(),idx[x].end(),l);
}

int ask(int l,int r)
{
    int bl=id[l],br=id[r];
    if(br-bl<=1)
    {
        int mx=0,res=0;
        for(int i=l;i<=r;i++)
        {
            int cnt_x=get_cnt(l,r,c[i]);
            if(cnt_x>mx||(cnt_x==mx&&c[i]<res))
            {
                mx=cnt_x;
                res=c[i];
            }
        }
        return val[res];
    }
    int res=p[bl+1][br-1];
    int mx=get_cnt(l,r,res);
    for(int i=l;i<=R[bl];i++)
    {
        int x=c[i];
        int cnt_x=get_cnt(l,r,x);
        if(cnt_x>mx||(cnt_x==mx&&x<res))
        {
            mx=cnt_x;
            res=x;
        }
    }
    for(int i=L[br];i<=r;i++)
    {
        int x=c[i];
        int cnt_x=get_cnt(l,r,x);
        if(cnt_x>mx||(cnt_x==mx&&x<res))
        {
            mx=cnt_x;
            res=x;
        }
    }
    
    return val[res];
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    init();
    while(m--)
    {
        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=ask(l,r);
        cout<<last<<'\n';
    }
    return 0;
}