题意

设 $a$ 的价值为 $a \times cnt_a$（$cnt_a$ 为 $a$ 在区间中出现的次数），求区间种某种元素，使得这种元素的价值最大。

因为设计出现元素的次数，所以首先考虑莫队。

由于 Add 操作很好写，Del 操作不会写，所以我们考虑一种专门处理 Del 不容易处理的莫队：回滚莫队。

回滚莫队将询问区间分为两部分。设 $[L,R]$ 的左端点 $L$ 所在块的右端点为 $p$，则将区间分为 $[L,p]$ 和 $[p,R]$。

我们发现对于左端点所在块不变的情况，右端点 $ R $ 是单调递增的，可以直接 Add；而左端点的数量级在 $O(\sqrt n)$ 级别，我们可以先只计算右边的区间的贡献，然后向左 Add，最后撤回向左的 Add。

因为向左的操作只有 $O(\sqrt n)$ 个，所以撤回操作的复杂度也是 $O(\sqrt n)$ 的。

不过这道题有一点儿细节，具体见代码。

#include<algorithm>

#include<cstdio>

#include<cmath>

const int M=1e5+5;

int n,m,p,a[M],CB[M],lsh[M];long long cur,tmp,ans[M];

int len,v[M],mdf[M];bool vis[M];

inline long long max(const long long&a,const long long&b){

	return a>b?a:b;

}

struct Query{

	int L,R,p,id;

	inline bool operator<(const Query&it)const{

		return p==it.p?R<it.R:L<it.L;

	}

}q[M];

inline void AddR(const int&val){

	cur=max(cur,1ll*++CB[val]*lsh[val]);

}

inline void AddL(const int&val){

	if(!vis[val]){

		++len;mdf[len]=val;v[len]=CB[val];vis[val]=true;

	}

	tmp=max(tmp,1ll*++CB[val]*lsh[val]);

}

signed main(){

	register int i,j,id;

	scanf("%d%d",&n,&m);p=ceil(n/sqrt(2.0*m/3));

	for(i=1;i<=n;++i)scanf("%d",a+i),lsh[++len]=a[i];

	std::sort(lsh+1,lsh+len+1);len=std::unique(lsh+1,lsh+len+1)-lsh-1;

	for(i=1;i<=n;++i)a[i]=std::lower_bound(lsh+1,lsh+len+1,a[i])-lsh;len=0;

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

		scanf("%d%d",&q[i].L,&q[i].R);

		q[i].p=(q[i].L-1)/p+1;q[i].id=i;

	}

	std::sort(q+1,q+m+1);

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

		const int&QL=q[i].L,&QR=q[i].R;

		if(i==1||q[i].p!=q[i-1].p){

			for(j=1;j<=n;++j)CB[j]=0;

			id=q[i].p*p;cur=0;

		}

		if((QL-1)/p==(QR-1)/p){

			tmp=0;

			for(j=QL;j<=QR;++j)AddL(a[j]);

		}

		else{

			while(id<QR)AddR(a[++id]);tmp=cur;

			for(j=QL;j<=q[i].p*p;++j)AddL(a[j]);

		}

		for(j=1;j<=len;++j)CB[mdf[j]]=v[j],vis[mdf[j]]=false;

		ans[q[i].id]=tmp;len=0;

	}

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

}

巴特西

AT1219题解

题意

最新文章

热门文章