普通莫队解决区间众数的个数

SP32900 KDOMINO - K-dominant array

P1997 faebdc 的烦恼

P3709 大爷的字符串题

被摩尔投票法洗脑半天，发现好像可以直接拿莫队写啊喂！

针对原数据离散化，后开一个计数器和一个存放数的数量的桶，每次添加都跟计数器取最大，每次减少都查询是否有多个众数，如果多个则最大不变，否则跟随减少。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,len,num[N],a[N],Q,ton[N],cnt[N],mx,ans[N];
int get(int x) {return x/len;}
struct node
{
	int l,r,k,id;
	bool operator < (const node &o) const {
		if(get(l) == get(o.l))
			return get(l)&1 ? r > o.r : r < o.r;
		return get(l) < get(o.l);
	}
} q[N];
void add(int x)
{
	ton[cnt[a[x]]]--; ton[++cnt[a[x]]]++;
	mx=max(mx,cnt[a[x]]);
}
void del(int x)
{
	ton[cnt[a[x]]]--;
	if(cnt[a[x]] == mx && ton[cnt[a[x]]] == 0) mx -- ;
	ton[--cnt[a[x]]]++;
}
int main()
{
	scanf("%d%d",&n,&Q); len=(int)sqrt(n)+1; 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memcpy(num,a,sizeof num); 
	stable_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;
	for(int i=1;i<=Q;i++) {scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k); q[i].id=i;}
	stable_sort(q+1,q+1+Q); int l=1,r=0;
	for(int i=1;i<=Q;i++)
	{
		int l1=q[i].l,r1=q[i].r;
		while(l < l1) del(l++);
		while(l > l1) add(--l);
		while(r < r1) add(++r);
		while(r > r1) del(r--);
		ans[q[i].id]= bool(mx*q[i].k >= (r1-l1+1));
	}
	for(int i=1;i<=Q;i++) puts(ans[i] ? "YES" : "NO");
	return 0;
}

放在这，怕我忘了 /ll