题解

· · 题解

关于 EI 的这个做法的讲解不多，我看了一会才懂，这里放一下较为详细的流程讲解（不含复杂度证明）

首先考虑经典不带修区间最大子段和问题的线段树做法，每个节点维护 tot, sum, pre, suf 分别表示当前节点所代表的区间 [l, r] 的总和，最大子段和，前缀最大子段和（必须包含 l），后缀最大子段和（必须包含 r）。

然后递归左右子树后 pushup 更新一下当前节点的答案。

当前节点的最大子段和从 左最大子段和，右最大子段和，左后缀 + 右前缀中取最大值。

当前节点的前缀最大子段从 左前缀，整个左区间 + 右前缀 中取最大值。

当前节点的后缀最大子段和从 右后缀，整个右区间 + 左后缀 中取最大值。

当前节点的总和就是左总和加右总和。

现在看看修改，如果一次区间加并没有导致决策发生变化（另一个子段的和超过了原先的子段称为该区间的决策变化），该区间的答案会增大 lx。（l 是这个区间原先的最大子段和选择的子段的长度，x 是本次修改给每个节点增加的值）

所以原先的 tot, sum, pre, suf 不在表示一个值，而是一个二元组 (l, v)，v 就是原来的值，l 是当前选择的区间的长度，用来在有修改的时候更新答案。

这样就可以写成一个一次函数来表示一个决策：y = lx+v，x 就表示决策所在的区间被整体加了多少。（分散加的话会在 pushup 中被更新）

那这是修改不使决策改变的情况，如果修改使决策改变了，原来的决策 (l_1, v_1) 变成了新的决策 (l_2, v_2)，相当于因为 x 的增大 y_1 = l_1x + v_1 变得比 y_2 = l_2x + v_2 小了。pushup 的时候不是给这两个决策取过 \max 吗？在取 \max 的时候顺便记录一下决策的阈值，详细地说：

在合并两个决策 p = (l_1, v_1) 和 q = (l_2, v_2) 时（不妨设 v_1 \geq v_2），由于初始时没有修改，所以肯定选 p，这个时候顺便记录一个阈值 x，代表当修改大于等于 x 的时候，决策就会改变（x 即为交点横坐标），若不会改变（交点在 y 轴左边）则 x = inf。

还有一个特殊情况，就是 l_1 < l_2 而且 v_1 = v_2，这个时候就选 q，x 记 inf。

一个节点的阈值代表当修改大于等于 x 时，它维护的三个决策 sum, pre, suf 中有一个会改变。（取 \min 即可）

然后在修改的时候，如果发生了决策改变，就直接重构这棵子树。（暴力更新左右子树然后 pushup）

看起来很暴力，但是复杂度是对的，EI 说是 O(n\log^3n + m\log^4n + q\log n)，具体证明可以看 EI 的博客。