P3709 大爷的字符串题

我是题面

神奇的阅读题，没有良好的语文功底可能就真的要拿10分了

很明显这道题的意思是求区间众数出现的次数的相反数

怎么维护呢？又没有强制在线，上莫队啊

(cnt[i])记录(i)出现的次数，(sum[i])记录出现i次的数有几个，(maxa)记录答案

好了，这道题我们做完了

下面放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<cmath>
#define ll long long
#define gc getchar
#define maxn 200005
using namespace std;

inline ll read(){
	ll a=0;int f=0;char p=gc();
	while(!isdigit(p)){f|=p=='-';p=gc();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
	return f?-a:a;
}int n,m,c1,block,a[maxn],b[maxn],ans[maxn];

struct ahaha{
	int id,l,r;
	inline bool friend operator<(const ahaha x,const ahaha y){
		if(x.l/block!=y.l/block)return x.l<y.l;
		return x.r<y.r;
	}
}q[maxn];

int maxa,cnt[maxn],sum[maxn];
inline void add(int x){
	--sum[cnt[x]];++cnt[x];
	++sum[cnt[x]];maxa=max(maxa,cnt[x]);  //如果有一个数出现次数比maxa多了，修改maxa
}
inline void del(int x){
	--sum[cnt[x]];--cnt[x];
	++sum[cnt[x]];if(!sum[maxa])--maxa;  //如果没有出现maxa次的数了，maxa-1
}  //为什么可以直接-1呢？因为如果没有出现这么多次的数了要么是变多了，要么是变少了，出现在这，肯定是变少了呀

int main(){
	n=read();m=read();block=sqrt(n);
	for(int i=1;i<=n;++i)
		a[i]=b[i]=read();
	sort(b+1,b+n+1);c1=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+c1+1,a[i])-b;
	for(int i=1;i<=m;++i)
		q[i]={i,read(),read()};
	sort(q+1,q+m+1);
	int l=q[1].l,r=l-1;
	for(int i=1;i<=m;++i){
		while(l<q[i].l)del(a[l++]);
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(r>q[i].r)del(a[r--]);
		ans[q[i].id]=-maxa;
	}
	for(int i=1;i<=m;++i)
		printf("%d
",ans[i]);
	return 0;
}

阅读题，代码很简单，所以自己打呗，不要复制哦