小A的柱状图

小A的柱状图

区间[L,R]中矩形的高度取决于[L,R]中高度的最小值。如果下一个矩形高度比当前矩形高度小，这块矩形的高度就不可能再成为满足条件的矩形的高度。于是就可以把高度比下一块矩形大的矩形都删掉，用一个高度为下一个矩形的高度，宽度为删掉的矩形宽度和下一个矩形宽度的累加和代替。
用单调栈维护，更新单调栈时更新答案。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=1e6+5;
LL st[MAX_N];
LL w[MAX_N];
int l,r;
int n;
LL ans=0;
LL a[MAX_N],b[MAX_N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)scanf("%lld",&b[i]);
    l=1,r=0;
    for(int i=1;i<=n+1;i++){
        LL tmp=0;
        while(l<=r&&st[r]>=b[i]){
            tmp+=w[r];
            ans=max(ans,(tmp)*st[r]);
            r--;
        }

        tmp+=a[i];

        r++;
        st[r]=b[i],w[r]=tmp;
        ans=max(tmp*b[i],ans);
    }

    //cout<<endl;
    printf("%lld\n",ans);
}