P2659 美丽的序列

题目链接

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

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1:

3

1 2 3

输出样例#1：

说明

样例解释选取区间［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);

}

巴特西

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

P2659 美丽的序列

题目链接

题目描述

输入输出格式

输入输出样例

说明

题解

代码

最新文章

热门文章

巴特西

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

P2659 美丽的序列

题目链接

题目描述

输入输出格式

输入输出样例

说明

题解

代码

最新文章

热门文章

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