数列分块入门 9 & 蒲公英

• https://www.luogu.com.cn/problem/P4168
• https://loj.ac/problem/6285
• http://www.lydsy.com/JudgeOnline/problem.php?id=2724

区间众数查询。

解法一

莫队，但是蒲公英有加密操作。

解法二

分块。

离散化+块内二分。

预处理出两块之间的众数。

将每一个数出现的位置塞进一个 vector，排序，在面对整块时选择一手二分。

#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
int n,bl,a[40010],q,cnt,val[40010],pos[40010],L[40006],R[40006];
vector<int> orz_twx[40006];
void discrete() {
	memcpy(val,a,sizeof a);
	sort(val+1,val+n+1);
	cnt=unique(val+1,val+n+1)-(val+1);
}
int query(int x) {
	return lower_bound(val+1,val+cnt+1,x)-val;
}
int tot[40006],now,ma,f[806][806];
void pre(int x) {
	now=ma=0;
	memset(tot,0,sizeof tot);
	for(int i=L[x];i<=n;i++) {
		if(++tot[a[i]]>ma||(tot[a[i]]==ma&&a[i]<now))
		    now=a[i],ma=tot[a[i]];
		f[x][pos[i]]=now;
	}
}
int lans=0;
int find(int x,int l,int r) {
	return upper_bound(orz_twx[x].begin(),orz_twx[x].end(),r)-lower_bound(orz_twx[x].begin(),orz_twx[x].end(),l);
}
void work(int x,int l,int r,int &ans,int &cnt) {
	int w=find(x,l,r);
	if(w>cnt||(w==cnt&&x<ans))
		cnt=w,ans=x;
}
int query(int l,int r) {
	int ans=0,cnt=0;
	if(pos[l]==pos[r]) {
		for(int i=l;i<=r;i++)
		    work(a[i],l,r,ans,cnt);
		return val[ans];
	}
	if(pos[l]+1<=pos[r]-1)
	    if(f[pos[l]+1][pos[r]-1])
	        work(f[pos[l]+1][pos[r]-1],l,r,ans,cnt);
	for(int i=l;i<=R[pos[l]];i++)
	    work(a[i],l,r,ans,cnt);
	for(int i=L[pos[r]];i<=r;i++)
	    work(a[i],l,r,ans,cnt);
	return val[ans];
}
int main() {
	scanf("%d %d",&n,&q);
	int bl=sqrt(log(n)/log(2)*n);
	int len=bl?n/bl:n;
	for (int i = 1; i <= n; i++) 
		scanf("%d",&a[i]);
	discrete();
	for(int i=1; i<=bl; i++)
		L[i]=(i-1)*len+1,R[i]=i*len;
	if(R[bl]<n) {
		L[bl+1]=R[bl]+1;
		R[++bl]=n;
	}
	for(int i=1;i<=bl;i++)
	    for(int j=L[i];j<=R[i];j++)
	        pos[j]=i;
	for(int i=1;i<=n;i++) {
		a[i]=query(a[i]);
	    orz_twx[a[i]].push_back(i);
	}
	for(int i=1;i<=bl;i++)
	    pre(i);
	for (int i = 1; i <= q; i++) {
		int x,y;
		scanf("%d %d",&x, &y);
		x=(x+lans-1)%n+1,y=(y+lans-1)%n+1;
		if(x>y)
		    swap(x,y);
		//printf("true is %d and %d
",x,y);
		printf("%d
",lans=query(x, y));
	}
	return 0;
}

如上为蒲公英的 AC 代码。