题解 | #小A的柱状图#

单调栈
对每个i求它最左和最右可以延伸到哪，然后维护这个延伸区间*i的高度的最大值即是答案

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pb push_back
#define IOS ios::sync_with_stdio(false)
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const int N=1e6+5;
int n;
int a[N],b[N];
int l[N],r[N];
vector <int > sta;
void solve()
{
    //右边，看最右延伸到哪
    _for(i,1,n)
    {
        if( sta.empty() || b[i] >= b[sta.back()] )
        {
           sta.pb(i);
        }
        else
        {
            while( !sta.empty() && b[i] < b[sta.back()] )
            {
                r[sta.back()]=i-1;
                sta.pop_back();
            }
            sta.pb(i);
        }
    }
    //栈里剩余元素说明可以延伸到n
    while( !sta.empty() )
    {
        r[sta.back()]=n,sta.pop_back();
    }
    //左边，看最左延伸到哪
    _rep(i,n,1)
    {
        if( sta.empty() || b[i] >= b[sta.back()] )
        {
           sta.pb(i);
        }
        else
        {
            while( !sta.empty() && b[i] < b[sta.back()]  )
            {
                l[sta.back()]=i+1;
                sta.pop_back();
            }
            sta.pb(i);
        }
    }
    //栈里剩余元素说明可以延伸到1
    while( !sta.empty() ) l[sta.back()]=1,sta.pop_back();

    ll ans=0;
    _for(i,1,n) ans=max(ans , b[i]*(a[r[i]]-a[l[i]-1]));//左右延伸区间的长度 * 高
    cout<<ans<<endl;
}
signed main()
{
    ///!!!
//    freopen("data.txt","r",stdin);
    //!!!
    IOS;
    cin>>n;
    _for(i,1,n)
    {
         cin>>a[i];
         a[i]=a[i-1]+a[i];
    }
    _for(i,1,n) cin>>b[i];
    solve();
}