P3709 大爷的字符串题脑子+莫队

简化题意：区间众数出现次数？？？

为什么？原因是，贪心的想，我们要划分成尽量少的严格递增序列，这样rp掉的最少。

设区间众数出现次数为 \(x\) ，那我们至少要分成 \(x\) 段严格上升序列。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define R register int

using namespace std;

namespace Luitaryi {

inline int g() { R x=0,f=1;

	register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;

	do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;

} const int N=200010;

int n,m,B,anss;

int a[N],b[N],c[N],d[N],ans[N],pos[N];

struct node {int l,r,id;

	inline bool operator < (const node& that) const

		{return pos[l]==pos[that.l]?pos[l]&1?r<that.r:r>that.r:l<that.l;}

}q[N];

inline void add(int x) {

	if(anss==c[x]&&d[c[x]+1]==0) ++anss;

	--d[c[x]],++c[x],++d[c[x]];

}

inline void sub(int x) {

	if(anss==c[x]&&d[c[x]]==1) --anss;

	--d[c[x]],--c[x],++d[c[x]];

}

inline void main() {

	n=g(),m=g(); B=sqrt(n);

	for(R i=1;i<=n;++i) a[i]=g();

	memcpy(b,a,sizeof b),sort(b+1,b+n+1);

	R tot=unique(b+1,b+n+1)-b;

	for(R i=1;i<=n;++i) a[i]=lower_bound(b+1,b+tot+1,a[i])-b-1;

	for(R i=1;i<=m;++i) q[i].l=g(),q[i].r=g(),q[i].id=i;

	for(R i=1;i<=m;++i) pos[i]=(i-1)/B+1;

	sort(q+1,q+m+1); d[0]=n;

	for(R i=1,l=1,r=0,LL,RR,id;i<=m;++i) {

		LL=q[i].l,RR=q[i].r,id=q[i].id;

		while(l<LL) sub(a[l++]);

		while(l>LL) add(a[--l]);

		while(r<RR) add(a[++r]);

		while(r>RR) sub(a[r--]);

		ans[id]=anss;

	} for(R i=1;i<=m;++i) printf("%d\n",-ans[i]);

}

} signed main() {Luitaryi::main(); return 0;}

2019.11.23

巴特西

P3709 大爷的字符串题脑子+莫队

最新文章

热门文章

巴特西

P3709 大爷的字符串题 脑子+莫队

最新文章

热门文章

P3709 大爷的字符串题脑子+莫队