题解：P5693 EI 的第六分块

· · 题解

KTT

谨以此文纪念这一道远超能力范围的题

前言

warning：本文主要介绍做法，不含时间复杂度证明

感谢 @dead_X 的讲解。

本题沿用了线段树维护 区间子段和+单点修改 的思路，本质上就是对 前缀最大、区间和、后缀最大 那一套的变形。

Part 1

考虑 区间子段和+单点修改 是怎么做的。

在线段树单个节点维护的区间中，令 pre 表示前缀最大值，suf 表示后缀最大值，sum 表示区间和，tot 表示区间最大子段和。

则 区间和并 (pushup) 的式子：

pre=\max(Lpre,Lsum+Rpre)\\ suf=\max(Rsuf,Lsuf+Rsum)\\ sum=Lsum+Rsum\\ tot=\max(Ltot,Rtot,Lsuf+Rpre)

当修改操作针对单点时，只需要底层修改+向上合并即可。

但是我们发现，线段树节点维护的四个值描述的是区间的最优连续结构，而压缩掉了具体的选取方案，当我们使用懒标记的思想进行区间操作，无法确定子树内的信息变化是否会对当前节点产生影响，因此朴素的延迟下放无法保正确性。

Part 2

考虑区间和 sum 在区间 +x 时如何变化

sum'=sum+(r-l+1)\times x

实际上是一个一次函数形式 kx+b，其中 k 是区间长度，x 表示作用在当前节点的增量。

同样的，pre、suf、tot 可以看作若干一次函数的和，也是一次函数形式。

表示的是：当前这个值为 b，若区间+x，这个值会变成 kx+b。

考虑为节点 p 做整体 +x 操作：

如果这一操作不足以使子树内合并时任何一次的 \max 取值改变，那么可以直接给节点打上懒标记，修改单个节点的信息。

否则内部合并过程有变化，至少有一个量的表达式会发生改变，需要递归进子树内进行修改。

Part 3

根据上述思路，我们发现在每一次 \max 合并时，不仅需要知道具体选取哪一个，还要知道 最小的 x 使得选取结果变化。

对于每个节点，维护一个阀值 m，表示修改量超过 m 时，子树内至少有一个 \max 取值变化。

容易发现 m 就是 {参与合并的一次函数交点、ls.m、rs.m} 最小值，特别的，底层节点 m=+\infty。

如果一次 +x 的修改延迟下放，那么 m\leftarrow m-x。

Part 4

考虑实现

1.直线类

struct line
{
    int k, b;
    inline line operator+(const line &other) const
    {
        return line{k + other.k, b + other.b};
    }
};

2.选取“当前值”较大的直线，并返回交点

pair<line, int> max(line a, line b)
{
    if (a.k < b.k || (a.k == b.k && a.b < b.b))
        swap(a, b);
    if (a.b >= b.b)
        return {a, INF};
    return {b, (b.b - a.b) / (a.k - b.k)};
}

3.线段树节点定义+合并信息

struct node
{
    line pre, suf, sum, tot;
    int m;
    inline node operator+(const node &other) const
    {
        node ans;
        ans.m = min(m, other.m);  //m取左右两边较小值
        pair<line, int> res;

        res = max(pre, sum + other.pre);
        ans.pre = res.first；
        ans.m = min(ans.m, res.second);  //m取交点最小值

        res = max(other.suf, suf + other.sum);
        ans.suf = res.first；
        ans.m = min(ans.m, res.second);

        res = max(tot, other.tot);
        ans.m = min(ans.m, res.second);
        res = max(res.first, suf + other.pre);
        ans.tot = res.first;
        ans.m = min(ans.m, res.second);
        ans.sum = sum + other.sum;

        return ans;
    }
} tr[N << 2];

4.修改作用在单点时

inline void work(int p, int w)
{
    tag[p] += w;
    tr[p].m -= w;
    tr[p].pre.b += tr[p].pre.k * w;  //作用在单点，修改“当前值”即可
    tr[p].suf.b += tr[p].suf.k * w;
    tr[p].tot.b += tr[p].tot.k * w;
    tr[p].sum.b += tr[p].sum.k * w;
}

7.pushup & pushdown

inline void pushup(int p)
    { tr[p] = tr[lc] + tr[rc]; }  //此处的加法为区间和并

inline void pushdown(int p)
{
    if (!tag[p])
        return;
    int w = tag[p];
    tag[p] = 0;
    work(lc, w), work(rc, w);
}

6.建树

void build(int p, int l, int r)
{
    if (l == r)
    {
        line t;
        t.k = 1, t.b = a[l];
        tr[p].m = INF, tag[p] = 0;
        tr[p].pre = tr[p].suf = tr[p].tot = tr[p].sum = t;
        return;
    }
    build(lc, l, mid), build(rc, mid + 1, r);
    pushup(p);
}

7.更新

void update(int p, int l, int r, int ql, int qr, int w)
{
    if (l >= ql && r <= qr)  //区间被完全覆盖，对整棵子树操作
    {
        if (tr[p].m >= w)  //修改量小于阀值，无需改变内部结构
        {
            work(p, w);  //直接修改单点即可
            return;
        }
        //修改量超过阀值，递归入子树修改
        pushdown(p);
        update(lc, l, mid, ql, qr, w), update(rc, mid + 1, r, ql, qr, w);
        if (l != r)
            pushup(p);
        return;
    }

    pushdown(p);
    if (ql <= mid)
        update(lc, l, mid, ql, qr, w);
    if (qr > mid)
        update(rc, mid + 1, r, ql, qr, w);
    pushup(p);
}

8.查询

//与普通线段树无异
node query(int p, int l, int r, int ql, int qr)
{
    if (l >= ql && r <= qr)
        return tr[p];
    pushdown(p);
    if (qr <= mid)
        return query(lc, l, mid, ql, qr);
    if (ql > mid)
        return query(rc, mid + 1, r, ql, qr);
    return 
        query(lc, l, mid, ql, qr) + query(rc, mid + 1, r, ql, qr); 
        //合并左右答案
}

9.主函数

signed main()
{
    n = read(), q = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    build(1, 1, n);
    while (q--)
    {
        int op = read();
        if (op == 1)
        {
            int l = read(), r = read(), x = read();
            update(1, 1, n, l, r, x);
        }
        else
        {
            int l = read(), r = read();
            printf("%lld\n", max(0LL, query(1, 1, n, l, r).tot.b));
            //注意query返回的是node，需要取实际值b。
        }
    }
    return 0;
}

\完结撒花/

码字辛苦，点个赞再走吧