洛谷 P2659 美丽的序列

题目背景

GD是一个热衷于寻求美好事物的人，一天他拿到了一个美丽的序列。

题目描述

为了研究这个序列的美丽程度，GD定义了一个序列的“美丽度”和“美丽系数”：对于这个序列的任意一个区间[l，r]，这个区间的“美丽度”就是这个区间的长度与这个区间的最小值的乘积，而整个序列的“美丽系数”就是它的所有区间的“美丽度”的最大值。现在GD想要你帮忙计算这个序列的“美丽系数”。

输入格式

第一行一个整数n，代表序列中的元素个数。第二行n个整数a1、a2„an，描述这个序列。

输出格式

一行一个整数，代表这个序列的“美丽系数”。

题解：

%%%JZW

如果要用线段树，需要枚举所有区间。

显然是不可的。

那么我们现在要求最大美丽度。我们思考剪去一些无用区间。

什么区间无用呢？贪心地思考，区间长度肯定是越大越好，那么对于一个点来讲，左右同时拓展这个区间，直到找到左右第一个小于它的元素，记作(l,r)，那么区间((l,r))一定是这个点能管控到的最大美丽值。因为这个点已经是这个区间中最小的元素。

那么所有点都可以依此维护，显然地，答案一定会在这些值中产生。理由是每个点都已经这样拓展过了，而每个点都是最优的。

至于左右第一个小于它的元素，可以用单调栈来维护，正反各跑一次，然后就是细节的更新了。

代码：

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=2e6+3;
int n,ans;
int a[maxn];
int s[maxn],top;
int l[maxn],r[maxn];
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	a[0]=a[n+1]=-1;
	for(int i=1;i<=n+1;i++)
	{
		while(top && a[i]<a[s[top]])
		{
			r[s[top]]=i;
			top--;
		}
		s[++top]=i;
	}
	while(top)
		top--;
	for(int i=n;i>=0;i--)
	{
		while(top && a[i]<a[s[top]])
		{
			l[s[top]]=i;
			top--;
		}
		s[++top]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int len=r[i]-1-l[i];
		int tmp=a[i]*len;
		ans=max(ans,tmp);
	}
	printf("%lld
",ans);
	return 0;
}