思路:
区间众数很容易想到莫队,但本题要求强制在线,莫队的在线化实现相当复杂,故采用分块。
先将a序列离散化,然后用朴素的方法处理出各大块之间的众数是多少。关于残块,不难发现众数只可能是残块中的数或大块间众数,故只需再统计各块中各数字出现次数,每次处理询问时比较至多 个数的出现次数即可。
顺带一提通常 的复杂度属于极差的复杂度,除非像C题那样严重卡空间否则尽可能不要使用。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mn 40005
#define mt 205
#define reg int //不能用register,心塞qwq
using std::memset;
using std::sort;
using std::swap;
int bl[mn],l[mt],r[mt],cnt[mt][mn],mo[mt][mt];
int a[mn],val[mn];
int tot[mn];
struct node {
int b,loc;
} o[mn];
inline bool cmp(node a,node b) {
return a.b<b.b;
}
inline int query(int le,int ri) {
memset(tot,0,sizeof tot);
reg L=bl[le],R=bl[ri]-1;
reg mode=mo[L+1][R],i;
reg mx=cnt[R][mode]-cnt[L][mode];
for(i=r[L]; i>=le; --i) {
reg num=(++tot[a[i]])+cnt[R][a[i]]-cnt[L][a[i]];
if(num>mx||num==mx&&a[i]<mode) mode=a[i],mx=num;
}
for(i=l[R+1]; i<=ri; ++i) {
reg num=(++tot[a[i]])+cnt[R][a[i]]-cnt[L][a[i]];
if(num>mx||num==mx&&a[i]<mode) mode=a[i],mx=num;
}
return val[mode];
}
int main() {
reg n,m,t,i,j,k,now=0,la=0,le,ri;
scanf("%d%d",&n,&m);
t=sqrt(n);
for(i=1; i<=n; ++i) bl[i]=(i-1)/t+1;
for(i=1; i<=bl[n]; ++i) l[i]=(i-1)*t+1,r[i]=i*t;
r[bl[n]]=n;
for(i=1; i<=n; ++i) {
scanf("%d",&o[i].b);
o[i].loc=i;
}
sort(o+1,o+1+n,cmp);
for(i=1; i<=n; ++i) {
if(o[i].b!=o[i-1].b) val[++now]=o[i].b;
a[o[i].loc]=now;
}
for(i=1; i<=bl[n]; ++i) {
reg mode=0x7f,mx=0;
for(j=1; j<=now; ++j) cnt[i][j]=cnt[i-1][j];
for(j=l[i]; j<=r[i]; ++j) ++cnt[i][a[j]];
for(j=i; j; --j) {
for(k=r[j]; k>=l[j]; --k) {
reg num=cnt[i][a[k]]-cnt[j-1][a[k]];
if(num>mx||num==mx&&a[k]<mode) mode=a[k],mx=num;
}
mo[j][i]=mode;
}
}
for(i=1; i<=m; ++i) {
scanf("%d%d",&le,&ri);
le=(le+la-1)%n+1,ri=(ri+la-1)%n+1;
if(le>ri) swap(le,ri);
la=query(le,ri);
printf("%d\n",la);
}
return 0;
}