「单调栈，单调队列」总结

整天做DP太累了……下午重新看了下有关单调栈的内容

单调栈用途就在于求一个数列中，某点左侧第一个比他大（或小）的元素位置。

假设维护一个单调上升的栈。如果入栈元素小于栈顶那么就要开始pop。而pop掉的元素一定全都大于这个入栈元素。单调栈内的两个相邻元素a,b如果在原序列中不是相邻的，则意味着b的出现pop掉了中间的元素，因此这中间的元素必定都大于b。

可以把单调栈的一个元素看做原序列的一块元素。b就代表了原序列中(a,b]

一个元素的进入弹掉了一部分元素，由此求出最左延伸量。如果一个元素即将被pop，意味着终于出现了一个比它小的，就可以求出最右延伸量了。

一个元素仅能进一次出一次，复杂度$O(n)$。

#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
inline int read(){
    int x(0),w(1); char c = getchar();
    while(c^'-' && (c<'0'||c>'9')) c = getchar();
    if(c == '-') w = -1, c = getchar();
    while(c>='0' && c<='9') x = (x<<3) + (x<<1) + c - '0', c = getchar();
    return x*w;
}
int n,a[100010],s[100010],top,l[100010],r[100010],sum[100010],L,R,ans=-0x3f3f3f3f;
signed main(){
//    freopen(".in","r",stdin);
    n = read();
    for(int i = 1; i <= n; ++i){
        a[i] = read();
        sum[i] = sum[i-1] + a[i];
    } 
    for(int i = 1; i <= n; ++i){
        while(a[s[top]] > a[i] && top > 0){
            r[s[top]] = i-1;
            --top;
        } 
        l[i] = s[top]+1;
        s[++top] = i;
    }
    while(top){
        r[s[top]] = n;
        --top;
    }
    for(int i = 1; i <= n; ++i){
        if(ans < (sum[r[i]]-sum[l[i]-1])*a[i]){
            ans = (sum[r[i]]-sum[l[i]-1])*a[i];
            L = l[i], R = r[i];
        }
    }
    printf("%lld
%lld %lld",ans,L,R);
    return 0;
}