大爷的字符串题 莫队

大爷的字符串题 莫队

首先这不是一道字符串题。需要仔细研究题的性质，我们会发现答案即为区间众数的个数，因为我们可以将区间分为众数个递增数列，这样为最优。

所以问题转换为求区间众数个数。使用莫队。

#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 400020
using namespace std;
int ans,a[MAXN],cnt[MAXN],sum[MAXN];
inline void add(int x){
	--sum[cnt[a[x]]];
	++cnt[a[x]];
	++sum[cnt[a[x]]];
	ans=max(cnt[a[x]], ans);
}
inline void del(int x){
	--sum[cnt[a[x]]];
	if(cnt[a[x]]==ans&&sum[cnt[a[x]]]==0) --ans;
	--cnt[a[x]];
	++sum[cnt[a[x]]];
}
struct nod{
	int l,r,qid,bid;
} q[MAXN];
bool cmp(const nod &a, const nod &b){
	return ((a.bid^b.bid)?a.l<b.l:((a.bid&1)?a.r<b.r:a.r>b.r));
}
struct pa{
	int val,pos;
} ta[MAXN];
bool cmp_pair(const pa &a, const pa &b){
	return a.val<b.val;
}
int n,m,blo,qres[MAXN];
int main(){
    freopen("testdata.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for(int i=1;i<=n;++i) scanf("%d", &ta[i].val), ta[i].pos=i;
	sort(ta+1, ta+1+n, cmp_pair);
	int idx=0;
	a[ta[1].pos]=idx;
	for(int i=2;i<=n;++i){
		if(ta[i-1].val!=ta[i].val) ++idx;
		a[ta[i].pos]=idx;
	}
	blo=n/sqrt(m*2.0/3);
	for(int i=1;i<=m;++i){
		scanf("%d %d", &q[i].l, &q[i].r);
		q[i].qid=i;
		q[i].bid=q[i].l/blo;
	}
	sort(q+1, q+1+m, cmp);
	int l=1,r=1;ans=1;cnt[a[1]]=1;sum[1]=1;
	for(int i=1;i<=m;++i){
		while(l<q[i].l) del(l++);
		while(l>q[i].l) add(--l);
		while(r<q[i].r) add(++r);
		while(r>q[i].r) del(r--);
		qres[q[i].qid]=ans;
	}
	for(int i=1;i<=m;++i) printf("%d
", -1*qres[i]);
	return 0;
}