定义与性质
\(\rm slope \ trick\) 通常用于维护 「线性分段凸函数」（如下图） 的相关转移 \(\rm dp\)。
形式化地说，其可以维护的函数 \(f(x)\) 满足：\(f(x)\) 在整数域上为连续凸函数，且考虑 \(f(x)\) 分段的断点 \(x_0, x_1, x_2, \cdots x_k, x_{k + 1} \in \mathbb{N}, x_0 = -\infty, x_{k + 1} = \infty\) 且形如 \(f(x) = k_ix + b_i(x_{i - 1} \le x \le x_i)\)
在此考虑如何维护之前，（不加证明地）给出「线性分段凸函数」的若干简单性质：
-
\(\forall d \in \mathbb{N}\) 若 \(f(x)\) 为「线性分段凸函数」则 \(f(x + d)\) 也为「线性分段凸函数」。
-
若 \(f(x), g(x)\) 均为「线性分段凸函数」则 \(h(x) = f(x) + g(x)\) 也为「线性分段凸函数」。
基本思路
其基本思路是按照直线斜率正负分开维护左右两个函数。
我们发现：若知道「线性分段凸函数」最低点 \(\min_f\) 与其在值域上 斜率变化量为 \(1\)（若变化量 \(\Delta d > 1\) 则看作这个位置斜率变化了 \(\Delta d\) 次） 的位置（以下简称断点）就可以与原函数构成双射。
因此，对于一个「线性分段凸函数」我们维护一下几个信息：
- 函数最小值 \(\min_f\)
- 函数斜率 \(< 0\) 的直线断点构成集合 \(L\)，斜率 \(> 0\) 的直线断点构成集合 \(R\)。
为了减少讨论，我们在 \(L, R\) 中事先分别加入 \(-\infty, \infty\) 两个断点。
第一种信息很方便维护，对于第二种信息通常需要使用堆或平衡树来维护。
常见操作
函数最小值
若需要求函数的最小值，显然直接调用维护的 \(\min_f\) 即可。
若需要求函数最小值对应的自变量取值，那么只需调用 \(L\) 集合内位置最大的断点 \(l\) 和 \(R\) 集合位置最小的断点 \(r\)，那么 \([l, r]\) 即为所求。
若操作二使用堆维护，单次复杂度 \(\mathcal{O}(1)\)；若操作二使用平衡树维护，单次复杂度 \(\mathcal{O}(\log n)\)。
函数平移
由性质一，可知「线性分段凸函数」平移后仍是「线性分段凸函数」，因此维护平移操作是可行的。
显然最小值不变，只需修改 \(L, R\) 两个集合。
考虑维护 \(L, R\) 两个集合坐标平移的变化量即可 \(\mathcal{O}(1)\) 维护。
简单函数的累加
常数函数 \(g(x) = c\)
显然最小值变化量 \(+c\)，\(L, R\) 两集合不变，简单 \(\mathcal{O}(1)\) 维护。
绝对值函数 \(g(x) = |x - c|\)
注意到 \(g(x)\) 为「线性分段凸函数」，由性质二 \(f(x) + g(x)\) 也为「线性分段凸函数」。
累加「线性分段凸函数」一般考虑分段依次加入，这样每次加入的都是一条直线。
下面以加入 \(x - c(x \ge c)\) 为例，\(-x + c\) 显然等价。
按照 \(c\) 与 \(max_L, min_R\) 的大小关系分类讨论。
- 若 \(c \le max_L\)
此时 \(max_L\) 会从 \(L\) 弹出加入 \(R\)，\(L\) 内会加入断点 \(c\)。
最小值 \(\min_f\) 的变化量为：\(max_L - sem_L\)（令 \(\max_L\) 为 \(L\) 一开始的最大值，\(sem_L\) 为 \(L\) 弹出 \(max_L\) 加入 \(c\) 后的最大值）
由于涉及到插入删除操作，使用堆或平衡树复杂度均为 \(\mathcal{O}(\log n)\)。
此时我们继续讨论剩下的两种情况，可以发现三种情况都可以简单地用 一种不需要讨论方式 维护：
令 \(max_L\) 为 \(L\) 在没有变化前的最大值。
将 \(c\) 插入 \(L\)，弹出 \(L\) 内最大元素至 \(R\)，令此时 \(L\) 内最大值为 \(sem_L\)。
令 \(\min_f \leftarrow \min_f + max_L - sem_L\)。
容易注意到，复杂度为单次 \(\mathcal{O}(1)\)。
函数最值操作
左取 \(\min\)：\(g(x) = \min\limits_{y \le x} f(y)\)
只需将 \(R\) 清空即可（注意保留 \(\infty\)），复杂度均摊单次 \(\mathcal{O}(\log n)\)。
右取 \(\min\)：\(g(x) = \min\limits_{y \ge x} f(y)\) 类似
区间左取 \(\min\)：\(\forall 0 \le a \le b, g(x) = \min\limits_{y \in [x - b, x - a]} f(y)\)
最小值 \(\min_f\) 不变。
\(L\) 集合向右整体平移 \(a\) 个单位，\(R\) 集合向右整体平移 \(b\) 个单位。
类似函数整体平移的方式维护，复杂度单次 \(\mathcal{O}(1)\)。
区间右取 \(\min\)：\(\forall 0 \le a \le b, g(x) = \min\limits_{y \in [x + a, x + b]} f(y)\) 类似
区间左取 \(\max\)：\(\forall 0 \le a \le b, g(x) = \max\limits_{y \in [x - b, x - a]} f(y)\)
分两类情况：
- \(b - a \le \min_R - \max_L\)
最小值 \(\min_f\) 不变。
\(L\) 集合向右整体平移 \(b\) 个单位，\(R\) 集合向右整体平移 \(a\) 个单位。
类似函数整体平移的方式维护，复杂度单次 \(\mathcal{O}(1)\)。
- \(b - a > \min_R - \max_L\)
也即对两个函数 \(L(x - b), R(x - a)\) 取较大者。
考虑维护 \(L, R\) 内第一个断点和第二个断点构成的线段 \(a, b\)。
每次弹掉 \(L, R\) 内第一个断点对应函数值较小的那个点直到 \(a, b\) 相交，令该点为 \(P\)。
则 \(\min_f\) 的值即为 \(P\) 在 \(a\) 上的取值，然后把 \(L, R\) 分别插入斜率变化量个 \(P_x\) 即可。
均摊复杂度单次 \(\mathcal{O}(\log n)\)，但因为 \(P_x\) 不一定为整数所有这类问题比较少见。
区间右取 \(\max\)：\(\forall 0 \le a \le b, g(x) = \max\limits_{y \in [x - b, x - a]} f(y)\) 类似