Slope trick 学习笔记
概述
Slope trick 是一种维护凸函数优化 dp 的方式。通过记录函数的转折点和最右段的一次函数，就可以表示出一个凸函数。
一个转折点 \(x\) 表示在 \(x\) 处斜率变化量为 1（由维护的是上凸壳或下凸壳决定），若在 \(x\) 处斜率差 \(a\) \(>1\)，就放置 \(a\) 个 \(x\)。通常在题目中，斜率和转折点都是整数，因此可以用一个堆 / 平衡树来存储所有转折点。
例如：\(f(x) = |x|\) 的转折点是 0，记录的序列是 \(\{0, 0\}\)。
性质：
两个凸函数 \(f(x), g(x)\)，设其所有转折点分别为 \(S_1, S_2\)，直线为 \(f_1, f_2\)，则 \(h(x) = f(x) + g(x)\) 也是凸函数，且满足 \(S_3 = S_1 +S_2, f_3 = f_1+f_2\)。
例 1：【CF713C】Sonya and Problem Wihtout a Legend
将 \(a_i \leftarrow a_{i} - i\)，转化为单调不降。设 \(dp_{i, j}\) 表示 \(a_i = j\) 时最小花费，则 \(dp_{i, j} = \min\limits_{k = 1}^{j}dp_{i - 1, k}+|a_i - j|\)。
设 \(g_{i, j}\) 为 \(dp_{I, j}\) 前缀最小值，则 \(dp_{I, j} = g_{i - 1, j}+|a_i - j|\)。 可归纳证明 \(dp_i, g_i\) 为下凸函数，且所有斜率都是整数。
由于 \(g_{i, j}\) 为 \(dp_{i, j}\) 前缀最小值，设最小值位置为 \(h\)。则 \(g_i\) 的图像和 \(f_i\) 几乎完全相同，且 \(x \geq h\) 后，\(g_i\) 为一条平行于 \(x\) 轴的直线。因此可以忽略 \(x \geq h\) 的所有转折点。
\(f_i\) 由 \(g_{i - 1}\) 加入 \(|x - a_i|\) 得到，根据凸函数性质，等价于加入 \(\{a_i, a_i\}\)。
当 \(h \leq a_i\) 时，所有斜率都应该 \(-1\)，\(a_i\) 变成新的 \(h\)，因此直接加一个 \(a_i\)。
当 \(h > a_i\) 时，原来的 \(h\) 应该被删去，新图像往上平移了 \(h - a_i\)，因此将答案加上 \(h - a_i\)，弹出 \(h\)，加入两个 \(a_i\)。
例 2：【11.04-NOIP模拟】最大值
设 \(dp_{x, i}\) 表示 \(x\) 子树中选择了 \(i\) 个点的最大距离和，则先由儿子背包得来，再 \(dp_{x, i} \leftarrow dp_{x, i} + w \times \min(i, k - i)\)。
经过归纳可知，\(dp_{x, i}\) 为下凸函数，证明如下：
两个凸函数的 \(\min, \ +\) 卷积为凸包的闵可夫斯基和，仍然是凸包，\(f(x) = w \times \min(x, k - x)\) 也是凸函数，因此 \(dp_{x}\) 是关于 \(i\) 的凸函数。
同时，两个凸函数的 \((\min, +)\) 卷积，等于其差分做归并排序