思路:

区间众数很容易想到莫队,但本题要求强制在线,莫队的在线化实现相当复杂,故采用分块。

先将a序列离散化,然后用朴素的方法处理出各大块之间的众数是多少。关于残块,不难发现众数只可能是残块中的数或大块间众数,故只需再统计各块中各数字出现次数,每次处理询问时比较至多 2S+12S+1 个数的出现次数即可。

顺带一提通常 O(n1.5log2n)O(n^{1.5}*log_2n) 的复杂度属于极差的复杂度,除非像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;
}