P8563 Magenta Potion 题解

前排警告

这是较为通用，不需要脑子，但是代码量巨大的题解，请谨慎食用

解题思路

不知道大家做没做过带修改的区间最大连续子段和，这一题其实就是带修改的区间最大连续子段积。

那么其实做法是类似的。

我们用线段树维护五个量：当前区间答案，区间前缀最小值，区间前缀最大值，区间后缀最小值，区间后缀最大值。

然后合并的时候分情况讨论：

1. 当前答案在左儿子区间内

2. 当前答案在右儿子区间内

3. 当前答案跨左，右儿子的区间

前两种情况直接得，最后一种情况就是左儿子区间的一个后缀称上右儿子区间的一个前缀的积取最大值。

但是，不同与区间最大连续子段和直接简单相加，由于负负得正，乘法最大值可以通过最大值 \(\times\) 最大值，最小值 \(\times\) 最小值，最大值 \(\times\) 最小值这几种方式来得到，所以维护前缀最小值和后缀最小值。

完整代码

很巨，建议自己打，加强印象。

#include<bits/stdc++.h>
#define MAXN 200010
#define lson now << 1
#define rson now << 1 | 1
#define INF 1073741825
using namespace std;
typedef long long ll;
struct sec{
    int l, r;
    ll mul;
    sec operator * (const sec &b){
        sec res;
        res.mul = this->mul * b.mul;
        res.l = min(this->l, b.l); res.r = max(this->r, b.r);
        return res;
    }
};
struct node{
    int l, r;
    sec max_pre, min_pre, max_lst, min_lst, max_res;
};
bool operator > (sec a, sec b){ return a.mul > b.mul; }
bool operator < (sec a, sec b){ return a.mul < b.mul; }
node tree[MAXN << 2];
int n, q;
int a[MAXN];
void push_up(node &now, node &ls, node &rs){
    now.max_res = max(ls.max_res, rs.max_res);
    now.max_res = max(now.max_res, ls.max_lst * rs.max_pre);
    now.max_res = max(now.max_res, ls.min_lst * rs.min_pre);
    now.max_res = max(now.max_res, ls.min_lst * rs.max_pre);
    now.max_res = max(now.max_res, ls.max_lst * rs.min_pre);
    if(ls.max_pre.r == ls.r){
        now.max_res = max(now.max_res, ls.max_pre * rs.max_pre);
        now.max_res = max(now.max_res, ls.max_pre * rs.min_pre);
    }
    if(ls.min_pre.r == ls.r){
        now.max_res = max(now.max_res, ls.min_pre * rs.min_pre);
        now.max_res = max(now.max_res, ls.min_pre * rs.max_pre);
    }
    if(rs.max_lst.l == rs.l){
        now.max_res = max(now.max_res, ls.max_lst * rs.max_lst);
        now.max_res = max(now.max_res, ls.min_lst * rs.max_lst);
    }
    if(rs.min_lst.l == rs.l){
        now.max_res = max(now.max_res, ls.min_lst * rs.min_lst);
        now.max_res = max(now.max_res, ls.max_lst * rs.min_lst);
    }
    if(now.max_res.mul >= INF) now.max_res.mul = INF;

    now.max_pre = ls.max_pre;
    if(ls.max_pre.r == ls.r){
        now.max_pre = max(now.max_pre, ls.max_pre * rs.max_pre);
        now.max_pre = max(now.max_pre, ls.max_pre * rs.min_pre);
    }
    if(ls.min_pre.r == ls.r){
        now.max_pre = max(now.max_pre, ls.min_pre * rs.min_pre);
        now.max_pre = max(now.max_pre, ls.min_pre * rs.max_pre);
    }
    if(now.max_pre.mul >= INF) now.max_pre.mul = INF;

    now.min_pre = ls.min_pre;
    if(ls.max_pre.r == ls.r){
        now.min_pre = min(now.min_pre, ls.max_pre * rs.max_pre);
        now.min_pre = min(now.min_pre, ls.max_pre * rs.min_pre);
    }
    if(ls.min_pre.r == ls.r){
        now.min_pre = min(now.min_pre, ls.min_pre * rs.min_pre);
        now.min_pre = min(now.min_pre, ls.min_pre * rs.max_pre);
    }
    if(now.min_pre.mul <= -INF) now.min_pre.mul = -INF;

    now.max_lst = rs.max_lst;
    if(rs.max_lst.l == rs.l){
        now.max_lst = max(now.max_lst, ls.max_lst * rs.max_lst);
        now.max_lst = max(now.max_lst, ls.min_lst * rs.max_lst);
    }
    if(rs.min_lst.l == rs.l){
        now.max_lst = max(now.max_lst, ls.min_lst * rs.min_lst);
        now.max_lst = max(now.max_lst, ls.max_lst * rs.min_lst);
    }
    if(now.max_lst.mul >= INF) now.max_lst.mul = INF;

    now.min_lst = rs.min_lst;
    if(rs.max_lst.l == rs.l){
        now.min_lst = min(now.min_lst, ls.max_lst * rs.max_lst);
        now.min_lst = min(now.min_lst, ls.min_lst * rs.max_lst);
    }
    if(rs.min_lst.l == rs.l){
        now.min_lst = min(now.min_lst, ls.min_lst * rs.min_lst);
        now.min_lst = min(now.min_lst, ls.max_lst * rs.min_lst);
    }
    if(now.min_lst.mul <= -INF) now.min_lst.mul = -INF;
}
void build(int now, int l, int r){
    tree[now].l = l; tree[now].r = r;
    if(tree[now].l == tree[now].r){
        tree[now].max_pre = tree[now].max_lst = tree[now].max_res = tree[now].min_pre = tree[now].min_lst = (sec){l, r, a[l]};
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    push_up(tree[now], tree[lson], tree[rson]);
}
void update(int now, int pos, int val){
    if(tree[now].l == pos && tree[now].r == pos){
        tree[now].max_pre = tree[now].max_lst = tree[now].max_res = tree[now].min_pre = tree[now].min_lst = (sec){tree[now].l, tree[now].r, val};
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(pos <= mid) update(lson, pos, val);
    else update(rson, pos, val);
    push_up(tree[now], tree[lson], tree[rson]);
}
node query(int now, int l, int r){
    if(tree[now].l >= l && tree[now].r <= r){
        return tree[now];
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else{
        node ls = query(lson, l, mid), rs = query(rson, mid + 1, r), res;
        res.l = l; res.r = r;
        push_up(res, ls, rs);
        return res;
    }
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    build(1, 1, n);
    // int cnt = 0;
    for(int i = 1; i <= q; i++){
        int op, x, y;
        scanf("%d%d%d",&op,&x,&y);
        if(op == 1) update(1, x, y);
        else{
            ll res = max(query(1, x, y).max_res.mul, 1ll);
            if(res >= INF) printf("Too large\n");
            else printf("%lld\n",res);
        }
    }
    return 0;
}