整天做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\n%lld %lld",ans,L,R);return 0; }
