传送门

最开始没想到这个模型。还贪心写了半天，发现是错的，贪不动。

这题关键在于模型的转化。转化后的题意就是求一个最长的区间，使得区间总和乘上区间最小数最小。

那其实和单调栈经典题目求最大矩形是差不多的，稍微有点不同的是本题可以看成矩形的宽度不是1，而是题目给定的数字……..

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
int n;
ll a[maxn], b[maxn], w[maxn], s[maxn];
int main()
{
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld",&a[i]);
        }
        a[n + 1] = 0;
        memset(s, 0, sizeof s);
        int p = 0;
        ll ans = 0, l = 1, r = 1;
        for(int i = 1; i <= n + 1; i++)
        {
            if(a[i] > s[p]) s[++p] = a[i], w[p] = a[i], b[p] = i;
            else
            {
                ll wid = 0;
                while(s[p] > a[i])
                {
                    wid += w[p];
                    if(ans < wid * s[p])
                    {
                        ans = wid * s[p];
                        r = i - 1;
                        l = b[p];
                    }
                    p--;
                }
                s[++p] = a[i]; w[p] = wid + a[i];
            }
        }
        cout<<ans<<endl<<l<<" "<<r<<endl;
    }
}