P3709 大爷的字符串题(莫队+结论)

题目

P3709 大爷的字符串题

做法

有一个显然的结论：一段区间里最小答案为众数的个数

用莫队来离线求众数

\(tmp_i\)表示出现\(i\)次的数的个数，\(num_i\)表示\(i\)出现的次数

缩小区间：答案可能减小，看答案所在的\(tmp\)是否不唯一

扩大区间：答案增大

Code

#include<bits/stdc++.h>

typedef int LL;

const LL maxn=1e6+9;

inline LL Read(){

	LL x(0),f(1); char c=getchar();

	while(c<'0' || c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0' && c<='9'){

		x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar();

	}return x*f;

}

struct node{

	LL l,r,id;

}qy[maxn];

LL n,m,ret;

LL ans[maxn],num[maxn],tmp[maxn],a[maxn],b[maxn],bel[maxn];

inline bool cmp(node xx,node yy){

    return bel[xx.l]<bel[yy.l] || (bel[xx.l]==bel[yy.l] && (bel[xx.l]&1?xx.r<yy.r:xx.r>yy.r));

}

inline void Modify(LL val,LL op){

	if(!op){

		if(ret==num[val] && tmp[ret]==1) --ret;

		--tmp[num[val]]; ++tmp[--num[val]];

	}else{

		if(ret==num[val]) ++ret;

		--tmp[num[val]]; ++tmp[++num[val]];

	}

}

int main(){

	n=Read(); m=Read();

	for(LL i=1;i<=n;++i) a[i]=b[i]=Read();

	std::sort(b+1,b+1+n);

	for(LL i=1;i<=n;++i) a[i]=std::lower_bound(b+1,b+1+n,a[i])-b;//,printf("%d ",a[i]);puts("");

	for(LL i=1;i<=m;++i) qy[i]=(node){Read(),Read(),i};

	LL pieces(sqrt(n)),size(n/pieces);

	for(LL i=1;i<=pieces;++i){

	    for(LL j=(i-1)*size+1;j<=i*size;++j)

	        bel[j]=i;

	}

	for(LL i=pieces*size+1;i<=n;++i)

	    bel[i]=pieces+1;

	std::sort(qy+1,qy+1+m,cmp);

	tmp[0]=n;

	LL nl(1),nr(0);

	for(LL i=1;i<=m;++i){

		LL ql(qy[i].l),qr(qy[i].r);

		while(nl<ql) Modify(a[nl++],0);

		while(nl>ql) Modify(a[--nl],1);

		while(nr<qr) Modify(a[++nr],1);

		while(nr>qr) Modify(a[nr--],0);

		ans[qy[i].id]=ret;

	}

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

	return 0;

}

巴特西

P3709 大爷的字符串题(莫队+结论)

题目

做法

Code

最新文章

热门文章