【Luogu P5048】[Ynoi 2019 模拟赛] Yuno loves sqrt technology III / 题解

Description

给你一个长为 n 的序列 a，m 次询问，每次查询一个区间的众数的出现次数，强制在线。

Idea

分块。

预处理每两块之间的众数出现次数；用 $vector$ 存每种数值对应的所有元素下标；记录每个元素在 $vector$ 里的位置。

询问时，整块之间的答案已经预处理出来了，考虑 $2\sqrt n$ 个边角元素。

对于左边的边角元素 x，我们在相应的 vector 里找到下标为 $p_x+ans$ 的元素y，若 $y\leqslant r$，则说明该数值在范围内有至少 $ans+1$ 个数，暴力更新答案即可。

对于右边的边角元素，类似地处理即可。

Code

#include <bits/stdc++.h>
#define maxn 500100
#define maxb 780
using namespace std;
void chkmax(int &x,int y){x=x>y?x:y;}
int n,m,len=778,f[maxb][maxb],cnt[maxn];
int tot,a[maxn],pos[maxn],num[maxn];
int ans,blo,id[maxn],L[maxb],R[maxb];
vector<int>v[maxn];
void Init(){
	blo=(n-1)/len+1;
	for (int i=1;i<=blo;++i)
		L[i]=R[i-1]+1,R[i]=i*len;
	R[blo]=n;
	for (int i=1;i<=blo;++i){
		memset(cnt,0,sizeof(cnt));
		for (int j=L[i];j<=R[i];++j) id[j]=i;
		for (int j=i;j<=blo;++j){
			f[i][j]=f[i][j-1];
			for (int k=L[j];k<=R[j];++k)
			chkmax(f[i][j],++cnt[a[k]]);
		}
	}
}
int Query(int l,int r){
	int res=0;
	if (id[l]==id[r]){
		for (int i=l;i<=r;++i) cnt[a[i]]=0;
		for (int i=l;i<=r;++i) chkmax(res,++cnt[a[i]]);
	}
	else{
		res=f[id[l]+1][id[r]-1];
		for (int i=l;i<=R[id[l]];++i){
			int it=pos[i];
			while(it+res<v[a[i]].size()&&v[a[i]][it+res]<=r) ++res;
		}
		for (int i=L[id[r]];i<=r;++i){
			int it=pos[i];
			while(it-res>=0&&v[a[i]][it-res]>=l) ++res;
		}
	}
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%d",a+i),num[i]=a[i];
	sort(num+1,num+1+n);
	int tot=unique(num+1,num+1+n)-num-1;
	for (int i=1;i<=n;++i){
		a[i]=lower_bound(num+1,num+1+tot,a[i])-num;
		v[a[i]].push_back(i),pos[i]=v[a[i]].size()-1;
	}
	Init();
	for (int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		x^=ans,y^=ans;
		ans=Query(x,y);
		printf("%d\n",ans);
	}
}