原题链接:
https://www.luogu.org/problem/AT1219
https://www.lydsy.com/JudgeOnline/problem.php?id=4241

人话题面: 给定一个长为n的序列,q次询问区间\([l,r]\)上【出现的数字a×它的出现次数\(cnt_a\)】的最大值

既然是如此熟悉的,查询区间上不同的数的个数,肯定会先想到用莫队来维护最大值,但是原来的莫队不完全适用了,维护最大值添加起来很容易,但是没办法删除(如果你超级强说不定可以但我不会),我能想到的只有\(O(n)\)暴力,显然不行。所以就有了:回滚莫队

我们都很清楚莫队对询问区间的排序方法带来的一种性质:左端点在同一个分块中的所有查询区间右端点单调递增。所以对于左端点在同一个块中的每个区间,我们都可以\(O(n)\)解决所有的右端点,并且由于右端点的单调递增,我们不需要回头删除数据。若分块时以\(\sqrt n\)为块的大小,那么一共有\(\sqrt n\)个块,所以复杂度为\(O(n\sqrt n)\)。【由于左端点在一个块中是无序的,所以我们可以将一个块内的左端点统一记为块的右端,每次查询到一个区间,就把左区间暴力移动到该查询区间的左端点,最坏移动\(\sqrt n\)次,有n个左端点,复杂度也为\(O(n\sqrt n)\)】

如果左右端点都在同一个分块中,那么显然这里暴力统计的最坏复杂度也只是\(O(\sqrt n)\),所以直接暴力。

综上我们可以看到,回滚莫队的总复杂度也还是\(O(n\sqrt n)\)【可以这样想,回滚莫队就是比普通莫队多了个右端点的\(O(n\sqrt n)\)的左移而已】。

这样子的复杂度过这一道题没有问题,莫队万岁!!!

代码:

把这个代码调对可是不容易呢!!!因为ATCoder的数据点太多了。洛谷RemoteJudge太慢了,建议左转BZOJ!

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int M=100100;
const int N=5050;
int n,m;
int a[M],b[M],c[M],be[M],cnt[M],cunt[M],br[M];
ll ans[M];
struct ques{
	int l,r,id;
}q[M];

inline int Read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline bool CMP(ques a,ques b){
	return (be[a.l]^be[b.l])?be[a.l]<be[b.l]:a.r<b.r;
}

int main(){
	n=Read(),m=Read();
	int sq=sqrt(n),up=ceil((double)n/sq);
	for(int i=1;i<=up;i++){
		br[i]=i*sq;
		for(int j=(i-1)*sq+1;j<=br[i];j++)
			be[j]=i;
	}
	br[up]=n;
	for(int i=1;i<=n;i++)
		a[i]=b[i]=Read();
	sort(a+1,a+n+1);
	int tot=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=n;i++)
		c[i]=lower_bound(a+1,a+tot+1,b[i])-a;
	for(int i=1;i<=m;i++){
		q[i].l=Read();
		q[i].r=Read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,CMP);
	int i=1;
	for(int k=0;k<=up;k++){
		int l=br[k]+1,r=br[k];
		ll now=0;
		memset(cnt,0,sizeof(cnt));
		for(;be[q[i].l]==k;i++){
			int ql=q[i].l,qr=q[i].r;
			ll tmp;
			if(be[ql]==be[qr]){
				tmp=0;
				for(int j=ql;j<=qr;j++)
					cunt[c[j]]=0;
				for(int j=ql;j<=qr;j++)
					tmp=max(tmp,1ll*++cunt[c[j]]*b[j]);
				ans[q[i].id]=tmp;
				continue;
			}
			while(r<qr)
				now=max(now,1ll*++cnt[c[++r]]*b[r]);
			tmp=now;
			while(l>ql)
				now=max(now,1ll*++cnt[c[--l]]*b[l]);
			ans[q[i].id]=now;
			while(l<br[k]+1)
				--cnt[c[l++]];
			now=tmp;
		}
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments