Slope Trick¶

对于凸线性分段函数 $f(x)$，我们定义 $L(f(x)) = \{x_i\}$ 为 $f(x)$ 分界点集合（这里集合为multiset）。分界点可以将 $(-\infty, +\infty)$ 分成若干段，即 $(-\infty, x_1), (x_1, x_2), \dots, (x_{siz}, +\infty)$，设第 $i$ 段的斜率为 $k_i$，那么有 $k_{i} = k_{i + 1} - 1, i \le siz$。如 $f(x) = \left|x - c \right|$ 有 $L(f(x)) = \{c, c\}$ 。

若 $h(x) = f(x) + g(x)$ ，则有 $L(h(x)) = L(f(x)) \cup L(g(x))$，其中 $f, g, h$ 均为凸线性分段函数。

CF713C¶

题意¶

长度为 $n$ 的数列，每次可以让一个位置 $+1,-1$，问最少操作多少次可以使得数列严格递增。

题解¶

首先令 $b_i = a_i - i$，所求即为 $b_i$ 单调不减，显然终态每个位置一定是 $b_i$ 中的某个数，因此可以很轻易的得到一个 $O(n^2)$ 的转移。

\[ f_{i, j} = \min\limits_{k \le j} f_{i-1, k} + \left|j - b_i\right| \]

考虑设 $F_i(x) = f_{i, x}, G_i(x) = \min\limits_{k \le x} f_{i, k}$，容易发现 $F,G, \left|x-b_i\right|$ 的函数图像满足凸线性分段函数，如果知道 $G_{i - 1}$ 就很容易得到 $F_i$ 的分界点集合。

考虑如何通过 $F_i$ 得到 $G_i$，由于 $G_i$ 代表的是 $F_i$ 的前缀最小值，因此我们可以发现 $G_i$ 仅需要将 $F_i$ 中表示斜率大于 $0$ 的分界点删除即可。由于 $L(F_i(x)) = L(G_i(x)) \cup L(\left|x-b_i\right|)$ 因此会发现 $F_i$ 的斜率大于 $0$ 的部分仅有一个，使用大根堆维护即可，每次插入分界点后pop掉最大的 $x$ 即可。

考虑如何计算答案，我们可以模拟一下 $F_i, G_i$ 整体的变化以及整体函数最小值的变化。

$F_1$ 的函数如下图，无论 $b_1$ 是多少最小值均为 $0$，与 $X$ 轴交点为 $(b_1, 0)$，我们这里假设 $b_1 = 0$。

$G_1$ 的函数如下图，此时大根堆的堆顶即为 $0$。

考虑 $b_2 > 0$，我们可以得到 $F_2$ 如下，发现最小值不会发生变换。

考虑 $b_2 < 0$ ，会发现会产生 $0 - b_2$ 的贡献，此时 $0$ 是大根堆堆顶。

可以发现如果 $b_i$ 大于此时大根堆的堆顶，则不会产生贡献，否则会产生 $Q.top() - b_i$ 的贡献。（证明摸了，挺简单的）

复杂度为 $O(n\log{n})$

CF1534G¶

题意¶

从 $(0, 0)$ 开始，每次可以免费向上或者向右移动，即 $(x, y)$ 移动到 $(x + 1, y)$ 或 $(x, y + 1)$。有 $n$ 个目标点，当位于 $(X, Y)$ 时攻击第 $i$ 个目标点 $(x_i, y_i)$ 的代价为 $\max(\left|X - x_i\right|, \left|Y - y_i\right|)$，求攻击完所有目标的最小代价。$(n\le 8\times 10^5)$

题解¶

对于某一个固定的路径，击打目标点 $(x_i, y_i)$ 的最优点一定落在 $y = -x + c$ 上，证明略了。

因此此题可以将坐标轴顺时针旋转45°转化为新的问题。

从 $(0, 0)$ 开始，$(x, y)$ 每次可以移动到 $(x + 1, y - 1)$ 或 $(x + 1, y + 1)$，有 $n$ 个目标点，位于 $(X, Y)$ 时攻击第 $i$ 个目标点 $(x_i, y_i)$ 的代价为 $\left|Y - y_i\right|$，我们也可以写出一个 $O(nW)$ 的转移，$W$ 为值域。 $$ f_{i, j} = \min\limits_{j - (x_i - x_{i-1}) \le k \le j + (x_i - x_{i-1})} f_{i-1, k} + \left|j - y_i\right| $$ 这里目标点是排序后的。设 $F_i(x) = f_{i, x}, G_i(x) = \min\limits_{j - (x_i - x_{i-1}) \le k \le j + (x_i - x_{i-1})} f_{i-1, k}$，这里 $F,G$ 依然是凸线性分段函数。这里和上一题不同的是 $\min$ 是一个范围，因此我们要维护一个最小值的下标范围 $[l, r]$。

设 $X = x_i - x_{i - 1}$，我们会发现每次取 $\min$ 会让 $l$ 左侧的分界点 $-X$，$r$ 右侧的分界点 $+X$，因此我们可以维护一个 $l$ 左侧的大根堆以及 $r$ 右侧的小根堆，每个堆维护一个 $bias$ 即可维护分界点的变化。

考虑加入 $\left|x - y_i\right|$，即分界点集合增加 $\{x, x\}$：

$x < l$，等价于将 $\{x, x\}$ 塞入大根堆，将大根堆堆首取出放入小根堆，产生 $l-x$ 的贡献
$x > $r，等价于将 $\{x, x\}$ 塞入小根堆，将小根堆堆首取出放入大根堆，产生 $x - r$ 的贡献
$l \le x \le r$，将一个 $x$ 塞入小根堆，一个 $x$ 塞入大根堆
每次从大根堆、小根堆堆首取值维护 $[l, r]$ 即可。