题解：P5693 EI 的第六分块

· · 题解

本题是区间加正数 + 区间最大子段和，关于单点修改 + 区间最大子段和可以参见我一直在咕的线段树博客【2.3】例题 1。

先思考一个问题：单点修改为什么不能直接转成区间加？

答：区间加完后我们不能直接确定一个区间的最优决策会变成什么，而单点修改是可以的（都是一个点了，肯定只能选当前位置或不选啦）。

因此，对于区间修改我们只能暴力修改子树，但这样复杂度就直接爆炸了。

不过，我们可以维护一些额外的信息，可以快速判断一个区间的决策是否会发生变化，从而减少暴力枚举子树时的枚举量。

首先我们得明确：一个决策是如何存储的？或者说，一个决策的形式是什么？

这就跟区间加的性质有关了。如果区间加 x 后决策的区间没变，那么区间最大子段和、区间前缀最大和、区间后缀最大和都会加上 len \times x，其中 len 为原来最优决策的区间长度。

这提示我们，我们除了要把这个决策没有区间加时的值存下来，还需要把决策的区间长度 len 存储下来。

对于一个决策，如果其本来的值为 val，区间整体加了 x，则这个决策的真实值为 len \times x + val。因此，如果要比较两个决策在区间整体加 x 时孰优孰劣，只需要比较 len_1 \times x + val_1 和 len_2 \times x + val_2。

这显然可以看作两个以 x 作为自变量的一次函数。我们要探讨的问题是如何判断一个区间的决策是否会更改，假设决策 1 本来更优，那么在 x 达到一定的值后，决策 2 会比决策 1 更优。这个时刻显然是 x 取到两个一次函数交点的时刻（特别的，因为 x 为正，所以当交点为负时相当于决策 2 永远不可能优于决策 1，这等价于交点处 x 为 \inf）。

而本题中有三个量需要决策（区间和决策永远是左右区间和相加），所以，只要 x 达到任意一个量的决策的交点时，就需要重构整棵子树。

对于每个节点维护一个值 x 表示该区间内区间加的值超过 x 时就要暴力重构，x 除了可能是三个量决策的交点，还要和左右子节点的 x 取 \min（左右区间的决策修改也会导致当前区间决策发生变化）。

这样本题就做完了。

复杂度……不会证（可以看这篇题解）。

以下是一些注意事项：

  1. 本题不卡常。

  2. 交点横坐标只需要保留整数。

其余的可以参考代码中的注释（如果有不懂的地方可以回复我，我会随时更新）。

以下是代码（应该比较好懂吧）：

#include<bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 4e5 + 9,INF = 1e15;
int n,m;
int a[N];
struct linear_func{//一次函数，本质存储的是决策
    int k,b;//k：最优决策区间的长度；b：最优决策的值
    void add(int v){
        b += k * v;
    }
};
linear_func operator+(linear_func f1,linear_func f2){//两个一次函数相加
    return (linear_func){f1.k + f2.k,f1.b + f2.b};
}
linear_func Max(linear_func f1,linear_func f2){//返回两个一次函数在 x = 0 （没有区间加操作）处取值更优者及两函数交点坐标
    if(f1.k < f2.k || f1.k == f2.k && f1.b < f2.b)//不明白为什么不交换会WA，有知道的大佬欢迎私信告诉我！
        swap(f1,f2);
    return (f1.b >= f2.b) ? f1 : f2;
}
int intersection(linear_func f1,linear_func f2){//两个一次函数交点坐标
    if(f1.k < f2.k || f1.k == f2.k && f1.b < f2.b)
        swap(f1,f2);
    if(f1.b >= f2.b)
        return INF;
    return (f2.b - f1.b + f1.k - f2.k - 1) / (f1.k - f2.k);
}
struct node{
    linear_func sum,val;//区间和、区间最大子段和 
    linear_func lsum,rsum;//前缀最大和、后缀最大和 
    int x;//区间加超过了 x 就要重构子树
};
node operator+(node lc,node rc){//合并两个节点的信息
    node ret;
    ret.x = min(lc.x,rc.x);
    ret.x = min(ret.x,intersection(lc.val,rc.val));
    ret.x = min(ret.x,intersection(Max(lc.val,rc.val),lc.rsum + rc.lsum));
    ret.x = min(ret.x,intersection(lc.lsum,lc.sum + rc.lsum));
    ret.x = min(ret.x,intersection(rc.rsum,rc.sum + lc.rsum));

  //这部分和单点修改 + 区间最大子段和是一样的，只是额外维护了一个最优决策的长度k。
    ret.sum = lc.sum + rc.sum;
    ret.val = Max(Max(lc.val,rc.val),lc.rsum + rc.lsum);
    ret.lsum = Max(lc.lsum,lc.sum + rc.lsum);
    ret.rsum = Max(rc.rsum,rc.sum + lc.rsum);

    return ret;
}
struct KTT{
    struct ktt_node{
        node u;
        int tag;
    } t[N << 2];
    bool in_range(int l,int r,int L,int R){
        return L <= l && r <= R;
    }
    bool out_range(int l,int r,int L,int R){
        return r < L || l > R;
    }
    void push_up(int root){
        t[root].u = t[lchild].u + t[rchild].u;
    }
    void make_tag(int root,int v){
        t[root].tag += v;
        t[root].u.x -= v;
        t[root].u.sum.add(v);
        t[root].u.val.add(v);
        t[root].u.lsum.add(v);
        t[root].u.rsum.add(v);
    }
    void push_down(int root){
        if(t[root].tag){
            make_tag(lchild,t[root].tag);
            make_tag(rchild,t[root].tag);
            t[root].tag = 0;
        }
    }
    void defeat(int root,int l,int r,int v){//将以root为根的子树暴力重构
        if(v > t[root].u.x){//区间的决策发生了变化，暴力重构
            int tmp = t[root].tag + v;//注意要把标记一起传下去，v包括了root节点祖先的标记
            t[root].tag = 0;
            defeat(lchild,l,mid,tmp);
            defeat(rchild,mid + 1,r,tmp);
            push_up(root);
        }
        else//否则可以直接更新区间信息，打标记即可
            make_tag(root,v);
    }
    void build(int root,int l,int r){
        if(l == r){
            linear_func tmp = (linear_func){1,a[l]};//叶节点的区间长度为1，所以k就只能为1了（不用考虑叶节点不选的情况，如果出现了负数在 cout 处有取 max 操作可以忽略）
            t[root].u = (node){tmp,tmp,tmp,tmp,INF};
            return;
        }
        build(lchild,l,mid);
        build(rchild,mid + 1,r);
        push_up(root);
    }
    void update(int root,int l,int r,int L,int R,int v){
        if(out_range(l,r,L,R))
            return;
        if(in_range(l,r,L,R)){
            defeat(root,l,r,v);
            return;
        }
        push_down(root);
        update(lchild,l,mid,L,R,v);
        update(rchild,mid + 1,r,L,R,v);
        push_up(root);
    }
    node query(int root,int l,int r,int L,int R){
        if(in_range(l,r,L,R))
            return t[root].u;
        push_down(root);
        if(R <= mid)
            return query(lchild,l,mid,L,R);
        if(L > mid)
            return query(rchild,mid + 1,r,L,R);
        return query(lchild,l,mid,L,R) + query(rchild,mid + 1,r,L,R);
    }
} ktt;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    ktt.build(1,1,n);
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int l,r,v;
            cin >> l >> r >> v;
            ktt.update(1,1,n,l,r,v);
        }
        else if(op == 2){
            int l,r;
            cin >> l >> r;
            cout << max(ktt.query(1,1,n,l,r).val.b,0ll) << '\n';
        }
    }
    return 0;
}