Luogu P2659 美丽的序列

单调栈

只是一个比较简单的单调栈题目。我们换一种思考方式，我们枚举每段数列的最小值，然后我们发现当ta所能成为最小值的范围越大，对最终的答案的贡献也就越大。所以我们考虑求出ta所能成为最小值的数列的范围。

这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值的位置的问题。这可以用单调栈来解决，我们维护一个单调递增的栈，每次栈顶的元素被弹出的值的位置就是我们所求的被弹的元素的右边第一个比ta小的值的位置。当前元素不在弹出栈顶元素的时候，我们就求出了当前的元素的左边第一个比ta小的值的位置。因为每一个数值仅仅进了一次栈，所以时间复杂度是\(O(n)\).

另外还有一个类似的题目，想要练习单调栈的童鞋可以写一写。

最后献上我丑陋的代码

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int n,top;
LL ans;
const int N=2000010;
int a[N],l[N],r[N],zhan[N];
inline int read()
{
    int x=0,y=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*y;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=n;++i)l[i]=0,r[i]=n+1;
    for(int i=1;i<=n;++i)
    {
        while(top&&a[zhan[top]]>=a[i])r[zhan[top--]]=i;
        l[i]=zhan[top];
        zhan[++top]=i;
    }
    for(int i=1;i<=n;++i)ans=max(ans,(LL)(r[i]-l[i]-1)*a[i]);
    cout<<ans;
    return 0;
}