[QOJ4215]Easiest Sum

波长 原：QOJ

数据范围较大，枚举 \(k\) 肯定不实际；发现修改次数多了之后其实最大子段和的变化不多，因此考虑枚举 \(x\)，表示使得序列的最大子段和 \(\le x\) 所需的修改次数；

要满足所有子段和均 \(\le x\)，尝试刻画修改序列：

令修改变化为 \(c\)，则有 \(c_i \ge 0\)，且 \(\forall [l,r] \subseteq [1, n]\)，\(\displaystyle\sum _{i=l}^r a_i - \sum _{i=l}^r c_i \le x\)，对 \(a,c\) 分别作前缀和得到 \(s, d\)，于是得到一个差分约束模型：

\[\begin{aligned} d_i &\ge d_{i-1}\\ d_r-s_r &\ge d_l-s_l-x\\ k&=d_n \end{aligned} \]

将 \(s_r-d_r\) 记为 \(w_r\)，则可等价为：

\[\begin{aligned} w_i &\le w_{i-1}+a_i\\ w_r &\le w_l+x \end{aligned} \]

在这样的差分约束下，从 \(0 \to n\) 最短路即为 \(s_n-k\) 的最大值，那么此时 \(k\) 最小。

发现这个答案其实是从 \(1\sim n\)，划分出 \(t\) 个不交子段，子段外的 \(a_i\) 相加再加上 \(tx\) 的最小值，而 \(t \le n\) 可以尝试直接枚举。

\[k_{\min}(x)=s_n-w_n=s_n-\min_{0 \le t \le n} \left\{s_n-f(t)+tx \right\} = \max_{0\le t \le n} \{f(t)-tx\} \]

此处 \(f(t)\) 表示将 \(a\) 划分为 \(t\) 个不交子段，子段之和的最大值。

\(k_{\min}(x)\) 的形式令人拉响警报，很明显，这是一个凸函数。然而暂且还想不到怎么求 \(f(t)\)。

\(f(t)\) 应该是个经典问题吧，只是我不会。

为避免模拟费用流（本质相同），考虑反悔贪心：先进行一次最大子段和的选取，然后发现后面的区间需要选取这里的子段和占有的地方，就必须先减掉这段子段的贡献，所以反悔策略呼之欲出：直接使用线段树维护区间取相反数，动态维护最大子段和就好了。

最后是求出 \(f(t)\) 后，答案应该怎么求。由于 \(k_{\min}(x)\) 是个凸函数，考虑答案实际上是：

\[\mathrm{ans}_0 \times k-\sum _{i=1}^k \sum _{x \le n}[k_{\min}(x) \le i] \]

实际上呈现出来的是一张图：用 \(y=k\) 去与凸包相交，那么这一个 \(k\) 造成的贡献就是交点的右边有多少个 \(x\) 整点。

如何求答案就是拿这个去交就行了。