2019 우 객 여름 방학 다 교 훈련소 (4 차 전)C 문제 시퀀스 (선분 트 리 + 단조 창고)

#include 
using namespace std;
const int MAXN = 3000005;
long long node[2][MAXN<<2];
long long per[MAXN];
long long a[MAXN], b[MAXN];
int l[MAXN], r[MAXN];
//    
inline void PushUp(int root)
{
    //    
    node[0][root] = max(node[0][root<<1], node[0][root<<1|1]);
    node[1][root] = min(node[1][root<<1], node[1][root<<1|1]);
}
//1.  
inline void BuildTree(int root, int l, int r)     //[l,r]       , root        
{
    if(l == r){
        //            
        node[0][root] = node[1][root] = per[l];    //      
        return ;
    }
    int mid = (l + r) >> 1;
    //      
    BuildTree(root<<1, l, mid);// 
    BuildTree(root<<1|1, mid + 1, r);// 

    //    (       )
    PushUp(root);

}
//    
inline long long QueryMax(int root, int l, int r, int L, int R)
{
    // root        , [l,r]      , [L,R]          
    if(L <= l && r <= R){
        //          ,        
        return node[0][root];
    }
    int mid = (l + r) >> 1;

    long long ans = -1e18;
    if(L <= mid)
        ans = max(QueryMax(root<<1, l, mid, L, R), ans);
    if(R > mid)
        ans = max(QueryMax(root<<1|1, mid + 1, r, L, R), ans);

    return ans;
}
//    
inline long long QueryMin(int root, int l, int r, int L, int R)
{
    // root        , [l,r]      , [L,R]          
    if(L <= l && r <= R){
        //          ,        
        return node[1][root];
    }
    int mid = (l + r) >> 1;

    long long ans = 1e18;

    if(L <= mid)
        ans = min(QueryMin(root<<1, l, mid, L, R), ans);
    if(R > mid)
        ans = min(QueryMin(root<<1|1, mid + 1, r, L, R), ans);

    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    per[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> b[i];
        per[i] = per[i - 1] + b[i];
    }
    //      [0, n]         per[1] - per[0]
    BuildTree(1, 0, n);
    stack<int> st;
    //  L[i]
    for(int i = 1; i <= n; i++){
        while(st.size() && a[st.top()] >= a[i]) st.pop();

        if(st.size() == 0) l[i] = 0;
        else l[i] = st.top();

        st.push(i);
    }

    while(st.size()) st.pop();

    //  R[i]
    for(int i = n; i >= 1; i--){
        while(st.size() && a[st.top()] >= a[i]) st.pop();
        if(st.size() == 0) r[i] = n;
        else r[i] = st.top() - 1;
        st.push(i);
    }

    long long ans = -1e18;

    for(int i = 1; i <= n; i++){
        if(a[i] >= 0){
            ans = max(ans, (QueryMax(1, 0, n, i, r[i]) - QueryMin(1, 0, n, l[i], i - 1)) * a[i]);
        }
        else{
            ans = max(ans, (QueryMin(1, 0, n, i, r[i]) - QueryMax(1, 0, n, l[i], i - 1)) * a[i]);
        }
    }

    cout << ans << endl;

    return 0;
}