[马蜂易读][有注释][0pts][过样例][求助不求调]

代码如下

#include<bits/stdc++.h>
#define I int
#define ox of[x]
#define oy of[y]
#define f(i,x,y) for(I i=x;i<=y;i++)
using namespace std;
const I N=4e4+1;
I n,m,nw,len,tot,l[N],r[N],of[N];
struct node{I id,v,w;}a[N];
struct op{I v,c;}md[201][201],kk;//mode是众数，不是脏话 
inline bool c1(node x,node y){return x.id<y.id;}
inline bool c2(node x,node y){return x.w<y.w;}
I mp[N],bk[201][N];//
inline void pre_build()
{ 
    cin>>n>>m;
    //分块预处理 
    len=sqrt(n),tot=n/len+(n%len!=0);
    f(i,1,tot)l[i]=(i-1)*len+1,r[i]=i*len;
    r[tot]=n;
    f(i,1,n)of[i]=(i-1)/len;
    //映射预处理 
    f(i,1,n)cin>>a[i].w,a[i].id=i;
    sort(a+1,a+1+n,c2);
    mp[a[1].v=1]=1;
    f(i,2,n)
        if(a[i].w==a[i-1].w)a[i].v=a[i-1].v;
        else a[i].v=a[i-1].v+1,mp[a[i].v]=a[i].w;
    nw=a[n].v;
    sort(a+1,a+1+n,c1); 
    //前缀和预处理
    f(i,1,tot)//处理1~i中j的出现次数 
    {
        f(j,1,n)bk[i][a[j].v]=bk[i-1][a[j].v];//优化->f(j,1,nw)bk[i][j]=b[i-1][j];
        f(j,l[i],r[i])bk[i][a[i].v]++;
    }
    f(i,1,tot)//处理i~j中众数(并且数值最小) 
    {
        I t[N]={};
        f(j,i,tot)
            f(k,l[j],r[j])
            {
                I u=a[k].v;t[u]++;
//              printf("[%d,%d]%d,%d| ",i,j,mp[u],t[u]);
                if(t[u]>md[i][j].c||t[u]==md[i][j].c&&u<md[i][j].v)
                    md[i][j].v=u,md[i][j].c=t[u];
            }
    }
}
inline I query(I x,I y)
{
    I t[N]={};
    op mx=kk;
    //块内处理 
    if(ox==oy)
    {
        f(i,x,y)
        {
            I u=a[i].v;t[u]++;
            if(t[u]>mx.c||t[u]==mx.c&&u<mx.v)
                    mx.v=u,mx.c=t[u];
        }
        return mp[mx.v];
    }I v[N]={},vr[N]={},cnt=0;
    mx=md[ox+1][oy-1];
    //处理[x,r[ox]],[l[oy],y],另外,ox=of[x],oy同理,意思为x所属块的编号 
    f(i,x,r[ox])
    {
        I u=a[i].v;t[u]++;
        if(!v[u])v[u]=1,vr[++cnt]=u,t[u]+=bk[oy-1][u]-bk[ox][u];
    }
    f(i,l[oy],y)
    {
        I u=a[i].v;t[u]++;
        if(!v[u])v[u]=1,vr[++cnt]=u,t[u]+=bk[oy-1][u]-bk[ox][u];
    }
    f(i,1,cnt)
    {
        I u=vr[i];
//      cout<<"{"<<mp[mx.v]<<"}";
        if(t[u]>mx.c||t[u]==mx.c&&u<mx.v)mx.v=u,mx.c=t[u];
    }
    return mp[mx.v];
} 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    pre_build();
    I x,y,lt=0;
    f(i,1,m)
    {
        cin>>x>>y;
        if((x=(x+lt-1)%n+1)>(y=(y+lt-1)%n+1))swap(x,y);
        cout<<(lt=query(x,y))<<'\n';
//      f(i,1,n)
//      {
//          cout<<a[i].w<<' ';
//          if(i%len==0)cout<<"| ";
//      }cout<<"\n\nbk:\n";
//      f(i,1,tot)
//      {
//          f(j,1,n)cout<<mp[bk[i][j]]<<' ';
//          cout<<"\n";
//      }
//      cout<<"\nmd:\n";
//      f(i,1,tot)
//      {
//          f(j,i,tot)
//              cout<<"["<<i<<","<<j<<"]="<<mp[md[i][j].v]<<",";
//          cout<<"\n";
//      }
    }
}

笨人讲一下自己的思路

预处理等等都一样，不解释。
对于query函数中处理覆盖广的块，
我的做法伪代码如下:

1.建立一个桶，并存储两个边角的数字出现次数。

2.在每种数字第一次被记录时加上其位于中部完整的块内的出现次数，再记录到数组vr中。

3.提前取出中部完整的块内的众数的最小值，再遍历数组vr中的数，取出来与之比较次数，更新答案。

我认为这是足够清晰的。