KTT

我们考虑传统的区间最大子段和方法，维护最大前后缀和 \(ls,rs\) 和最大子段和 \(mx\)，这些东西直接区间加是不好维护的。但我们发现，设选择的长度是变量 \(x\)，区间加上的值为 \(k\)，这些东西都可以写成一个 \(kx+b\) 的一次函数形式，考虑维护这些一次函数。 具体的，我们在 ......

非常有道理。orz EI。 首先单点修改区间最大子段和是 GSS 的经典问题。我们维护出区间和 \(sm\)、最大前缀和 \(lmx\)、最大后缀和 \(rmx\)、最大子段和 \(mx\)，发现这是一种半群信息，直接线段树维护就可以了。 那么对于区间加正数问题，我们依然考虑线段树。线段树想要 pu ......