题解：P5693 EI 的第六分块

· · 题解

单点修改和区间最大子段和相信大家都会了。

但是本题是区间加正数，就比较难做了。因为区间加后，我们无法快速判断它对答案的贡献。

回忆单点修改和区间最大子段和的做法，我们分别维护了，区间和，区间前缀最大子段和，区间后缀最大子段和，与区间最大子段和。合并答案就不再说了。我们可以将这些值看做区间内的决策。

比如这样的一个数列：\{ 5 ,-9 ,5 ,5 ,-12 ,8\}。

显然，它的和为 2，前缀最大子段和为 6，后缀最大子段和为 8，最大子段和为 10。

则我们称其决策的区间分别为 [1,6],[1,4],[6,6],[3,4]。

区间和很好维护，因为其决策的区间始终为整个区间，设区间长度为 l，区间增量为 v，显然其对结果增加 l \times v。

最大子段和不好维护，因为其决策的区间是可变的。倘若其决策区间不可变，设决策区间长度为 l，区间增量为 v，显然其也可以对结果增加 l \times v。

不过决策区间也不是一定会变，当我们的增量比较小，则它可能不会使决策区间改变。容易发现它的决策区间改变存在某个值域 [x,\infty]，计算出这个阈值 x 或许可以实现快速地修改。

考虑将每个值维护成一次函数 ax+b 的形式。a 代表决策区间的长度，b 代表函数值，也就是我们维护的值，x 是我们每次操作的增量。

考虑计算阈值，先举一个前缀最大子段和的例子：

已知前缀最大子段和有两种取值，即左区间的前缀最大子段和，或左区间的和加上右区间的前缀最大子段和。

将其理解为两种不同的决策，这两种决策我们也表示为一次函数，也就是直线。

两条直线的交点就是区间前缀最大子段和决策变更的地方。注意如果不存在交点，阈值记为 \infty。

其余同理。

由于前缀最大子段和，后缀最大子段和，与区间最大子段和都会影响我们的答案，所以当增量大于这些值的阈值的最小值换一种方式修改，否则直接修改。注意直接修改对区间的阈值有影响，相当于做减法。

为了方便，不管我们是否改变决策，我们都先执行后者，此时阈值可能是负数。我们对当前节点为根构成的子树暴力重构，向下递归直到阈值是一个非负数。

说是暴力重构，其实 pushdown 一遍，再 pushup 一遍就好了。

这个问题就解决了。时间复杂度被证明为 O((n+q)\log^3 n)，但我不会证明。

阈值的极值一定要够大，否则会导致 RE 或 WA。