洛谷P2659 美丽的序列 单调栈模板

P2659 美丽的序列

题目链接

https://www.luogu.org/problemnew/show/P2659

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1:

3

1 2 3

输出样例#1：

4

说明

样例解释 选取区间［2，3］，可以获得最大“美丽系数”为2*2=4。 数据范围 对于20%的数据，n<=2000； 对于60%的数据，n<=200000； 对于100%的数据，1<=n<=2000000，0<=ai<=2000000。 提示 你可能需要一个读入优化。

题解

单调栈板子题，当然也可用笛卡尔树来做，不过没有必要。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define N 2000050

ll n,a[N],L[N],R[N],sk[N],ans;

template<typename T>void read(T&x)

{

  ll k=0; char c=getchar();

  x=0;

  while(!isdigit(c)&&c!=EOF)k^=c=='-',c=getchar();

  if (c==EOF)exit(0);

  while(isdigit(c))x=x*10+c-'0',c=getchar();

  x=k?-x:x;

}

void read_char(char &c)

{while(!isalpha(c=getchar())&&c!=EOF);}

int main()

{

#ifndef ONLINE_JUDGE

  freopen("aa.in","r",stdin);

#endif

  read(n);

  for(int i=1;i<=n;i++) read(a[i]);

  a[n+1]=-1;

  int top=0;

  for(int i=1;i<=n+1;i++)

      {

          while(top&&a[i]<a[sk[top]])R[sk[top--]]=i;

          L[i]=sk[top];

          sk[++top]=i;

      }

  for(int i=1;i<=n;i++)

      ans=max(ans,(R[i]-L[i]-1)*a[i]);

  printf("%lld",ans);

}