2019牛客暑期多校训练营(第四场场)_C题sequence(线段树+单调栈)

题目链接: https://ac.nowcoder.com/acm/contest/884/C

题意：给你两个长度为n的序列 a, b, 选一个子区间[l, r], 会得到一个值为 a序列在[l, r] 中的最小值 乘上 b序列[l, r]的和, 问这个值最大是多少？

思路：

• 首先， 我们记录下 以当前这个数a[i], 它在那个区间内是最小值, 记录 L[i], R[i]
• 然后我们用线段树维护前缀和
• 当a[i] 大于等于0 时，最大值就是这个数a[i] 乘上 和最大的那个区间(即，在[i, R[i]] 中的前缀和最大值 - 在[L[i], i - 1] 中的前缀和最小值)
• 当a[i] 小于 0 时，要使得值最大，即使得区间值最小, 所以就是 a[i] 乘上 （在[i, R[i]] 中的前缀和最小值 - 在[L[i], i - 1] 中的前缀和最大值)

参考博客

• https://www.cnblogs.com/wuliking/p/11261576.html
• https://blog.csdn.net/anthony1314/article/details/97535853

代码

#include <bits/stdc++.h>
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;
}