newcoder 小A的柱状图（单调栈）题解

#include<cmath>
#include<set>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e6 + 10;
const ull seed = 131;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
struct node{
    ll hei;
    int pos;
    node(int p = 0, ll h = 0): pos(p), hei(h){}
}s[maxn];
ll sum[maxn], h[maxn];
int n, top;
ll solve(){
    ll ans = 0;
    top = 0;
    for(int i = 1; i <= n; i++){
        if(top == 0 || h[i] >= s[top].hei) s[++top] = node(i, h[i]);
        else{
            int r, l;
            while(top > 0 && s[top].hei > h[i]){
                r = i - 1;
                l = (top == 1? 0 : s[top - 1].pos);
                ans = max(ans, s[top].hei * (sum[r] - sum[l]));
                --top;
            }
            s[++top] = node(i, h[i]);
        }
    }
    if(top > 0){
        int r, l;
        r = s[top].pos;
        while(top > 0){
            l = (top == 1? 0 : s[top - 1].pos);
            ans = max(ans, s[top].hei * (sum[r] - sum[l]));
            --top;
        }
    }
    return ans;
}
int main(){
    scanf("%d", &n);
    sum[0] = 0;
    for(int i = 1; i <= n; i++){
        scanf("%lld", &sum[i]);
        sum[i] += sum[i - 1];
    }
    for(int i = 1; i <= n; i++)
        scanf("%lld", &h[i]);
    printf("%lld\n", solve());
    return 0;
}