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

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

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

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

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

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

 

#include 
     
      #include 
      
       #include 
       
        #define int long longusing 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\n%lld %lld",ans,L,R);    return 0;}