自动搬运

查看原文

来自洛谷，原作者为

	iMya_nlgau ありがとう

搬运于2025-08-24 22:28:10，当前版本为作者最后更新于2022-01-14 10:51:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为这是一道黄题，所以不用主席树或者莫队这些算法。

我们对每种颜色开一个 vector 存下该颜色出现位置的下标，这样给定一个区间 $[l,r]$ 和一个颜色 $c$ 我们就可以在 vector 里二分求出 $[l,r]$ 中 $c$ 出现的次数，具体地，v[c] 表示颜色 $c$ 下标的 vector，那么

upper_bound(v[c].begin(),v[c].end(),r)-lower_bound(v[c].begin(),v[c].end(),l);

就是 $[l,r]$ 中 $c$ 出现的次数。

然后再考虑，如果一个颜色 $c$ 在长度为 $k$ 的区间里出现了超过 $\dfrac{k}{2}$ 次，那么我们在这个区间里随机 $t$ 次，每次随机一个位置，遇不到 $c$ 的概率小于 $\dfrac{1}{2^t}$，当 $t$ 取 $50$ 的时候这个概率大约是 $10^{-15}$，可以认为不可能发生。

所以对于每个询问 $[l,r]$，我们在 $[l,r]$ 中随机 $t$ 次，再判断每次随机到的颜色出现次数是否大于 $\dfrac{r-l+1}{2}$ 即可。

时间复杂度 $O(mt\log n)$，$t$ 为随机次数。$t$ 取 $20$ 的话我的代码是目前最优解。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;

inline int read(){
	int x=0; char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+(c^'0'),c=getchar();
	return x;
}

const int maxn=3e5+10;
const int maxm=1e4+10;

int n,c,m,a[maxn];
vector<int> v[maxm];

inline int query(int l,int r){
	for(int t=1;t<=50;t++){
		int p=l+rand()%(r-l+1);
		int res=upper_bound(v[a[p]].begin(),v[a[p]].end(),r)
			-lower_bound(v[a[p]].begin(),v[a[p]].end(),l);
		if(res>(r-l+1)/2) return a[p];
	}
	return -1;
}

int main(){
	srand((unsigned)time(NULL));
	
	n=read(),c=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),v[a[i]].push_back(i);

	for(int i=1;i<=c;i++) v[i].push_back(n+1);
	
	m=read();
	while(m--){
		int l=read(),r=read();
		int ans=query(l,r);
		if(~ans) printf("yes %d\n",ans);
		else puts("no");
	}
	
	return 0;
}