我们知道，对于具有凸性的DP存在一种技巧叫 Slope Trick，一般指利用堆维护斜率拐点，但凸壳不止这一种表达方法，还有一些。
先来看看我们需要的操作：
-
加法：\(g(x)=f(x)+h(x)\)，\(h_1(x)=C,h_2(x)=kx+b,h_3(x)=|x-a|\)
-
平移，然后取极值——这本质是闵可夫斯基和（负数下标就平移）
-
做闵可夫斯基和
与一个较小的凸壳做卷积。
-
前后缀极值
\(f'_x=\min_{y\le x}f_y\)。
-
\(f'_x=\min_{x-r\le y\le x-l}f_y\)
-
截断：
\(f'_x=\min(f'_{x-1}+k,f_x)\)
然后有一些常用的方法：
-
维护斜率变化点
Slope Trick 的经典办法，即维护所有的斜率转折点，也就是比如在 \(x>t\) 的所有斜线的斜率全部增加 \(1\)，那么就插入一个 \(t\)。实质上是斜率数组的差分的另一种表达（\(k_{i+1}-k_i\) 就是数字 \(i\) 出现次数）。一般用堆维护。
它丢失了具体的一个点信息，一般可以考虑维护图像的起点，以及首条斜线的斜率信息。
然后就可以逐个还原出斜率数组进而还原图像。
-
加常函数就改起点，加 \(kx+b\) 可以看出来是给所有直线斜率加，那么打一个全体加标记，加绝对值函数相当于值 \(a\) 左侧斜率减一，右侧加一，插入两个 \(a\) 并更新维护的额外信息即可。
-
平移就给起点打标记。
-
做不了闵可夫斯基和。
例如 \(f'_x=\min(f_{x},f_{x-1}+v_1,f_{x-2}+v_2)\)。
本质上是与 \(\lbrace 0,v_1,v_2\rbrace\) 做闵可夫斯基和。
-
相当于将斜率为正/负的段全部删掉，一般是用对顶堆维护 \(\le 0\) 和 \(>0\) 的部分，这也更方便维护最值。
-
这是特殊的闵可夫斯基和。
做适当的平移后，相当于扩展了最值的位置。
一般也考虑用对顶堆维护，但我们还需要额外增加变量来表示最值段的长度。
变化点集合有整体的加减标记，可以打 tag。
是 \(O(1)\) 的，这很重要。
-
这样的操作本质上是在删除斜率 \(>k\) 的部分。
弹出这些变化点即可。其实是上上个操作的简化版。
优点：相当于维护斜率的差分数组，但是避免了显式维护，这样可维护的值域之类都变大了。
缺点：做不了闵可夫斯基和，需要额外维护起点，最值相关信息。
-
-
维护斜率数组。
一般考虑采用堆，
map，set，平衡树，对顶堆，左偏树等有序且支持插入的结构。-
加一次函数相当于区间加，加绝对值也差不多，但支持定义域限制。
对于特定结构，例如对顶堆加 \(a=0\) 的绝对值函数也可以打标记做。
-
维护平移下标。
-
归并排序，或者直接将另一个凸壳并入有序结构。
用
set，堆，平衡树等都能做。 -
相当于在斜率归零的前/后赋 \(0\)。
可以考虑平衡树维护，可以考虑对顶堆直接清空一侧。
-
当闵可夫斯基和做，\(O(r-l)\)。复杂度较劣。
-
区间赋值，二分到相应位置。
只有 \(k=0\) 好做。这时候退化为 4.
否则就涉及区间覆盖操作了，只能用平衡树之类的做。
优点：可以很快速做闵可夫斯基和。
缺点：所需长度要有限，维护复杂度较高，且维护操作比较复杂，涉及到区间操作一般就只能上平衡树了。
-
-
维护斜率变化总量。abc217H
维护斜率变化点的更进一步形式，维护二元组 \((p,\Delta)\) 表示将斜率的差分数组 \(c_p\) 加上 \(\Delta\).
基本可以照搬斜率变化点的方法，但是需要注意二元组的合并（表达插多个的意思）。
-
维护凸壳顶点。
什么都能做。
做不了加法，代价非常大。
-
平衡树暴力维护分段一次函数。
直接存下每一段斜率对应的初始位置和结束位置，或者斜率变化点，用平衡树维护。
重型武器，全都能做，但是常数很大，代码很长，风险高
-
维护分段函数
有时候不止是一次函数，可能涉及高次函数，一般只能如此暴力处理。
附赠 AI 回答：
在 DP 优化和 Slope Trick 的语境下，“凸壳”指的是动态规划的状态函数 \(f(x)\) 的图像（因为它是一个凸函数）。
对凸壳的操作，本质上就是函数变换。我们需要根据这些数学变换，找出对应的数据结构（通常是双堆）的操作。
以下是常见的凸壳操作、几何含义及其实现方式：
1. 点加 (Pointwise Addition)
公式： \(g(x) = f(x) + h(x)\)
这是最基础的操作。根据 \(h(x)\) 的不同，处理方式也不同：
- 加常数： \(h(x) = C\)
- 含义：整个图像向上平移。
- 操作：
min_val += C。不影响斜率和拐点，只影响记录的最小函数值。
- 加一次函数： \(h(x) = kx + b\)
- 含义：图像发生倾斜（旋转）。
- 操作：这会改变所有线段的斜率。
- 如果在数据结构中维护的是“绝对斜率”，则需要打全局标记。
- 但在 Slope Trick 的双堆实现中，堆维护的是“斜率变化的位置（拐点）”。加线性函数不会改变拐点的 \(x\) 坐标，只会改变最底部的那个平坦段的斜率值（比如从 0 变成 \(k\)）。通常通过调整记录“最小值位置”的逻辑来处理，或者忽略它（如果只需要求最终的最值）。
- 加 V 型函数（核心）： \(h(x) = |x - a|\)
- 含义：在 \(x=a\) 处，左侧斜率 -1，右侧斜率 +1。
- 操作：向左堆 \(L\) 插入 \(a\)，向右堆 \(R\) 插入 \(a\)。
- 注：如果是加一般的凸函数，可以分解为多个 \(|x-a|\) 的叠加。
2. 坐标平移 (Translation / Shift)
公式： \(g(x) = f(x - c)\)
- 含义：整个图像向右平移 \(c\) 个单位。
- 几何：所有的拐点 \(x\) 坐标都变成了 \(x + c\)。
- 操作：
- 使用 Lazy Tag。
- 维护全局变量
lazy_L和lazy_R。 - 当
push元素时，存入val - lazy；当pop或top时，读出val + lazy。 - 操作：
lazy_L += c; lazy_R += c;
3. 取前缀/后缀最小值 (Prefix/Suffix Min)
公式： \(g(x) = \min_{y \le x} f(y)\) （前缀最小）
公式： \(g(x) = \min_{y \ge x} f(y)\) （后缀最小）
- 含义：将图像的一侧“拉平”。
- 前缀最小：图像右侧斜率 \(>0\) 的部分全部变成斜率 \(=0\)。
- 后缀最小：图像左侧斜率 \(<0\) 的部分全部变成斜率 \(=0\)。
- 操作：
- 对于 \(\min_{y \le x}\)：清空右堆 \(R\)（或者不断 pop 直到空）。此时函数在最低点及其右侧变成水平线。
- 对于 \(\min_{y \ge x}\)：清空左堆 \(L\)。
4. 窗口最小值 / 扩展 (Sliding Window Min / Expansion)
公式： \(g(x) = \min_{x - r \le y \le x - l} f(y)\)
这等价于 \((\min, +)\) 卷积的一个特例：\(g(x) = \min_y (f(y) + h(x-y))\)，其中 \(h(x)\) 是在区间 \([l, r]\) 取值 0，其他地方取 \(\infty\) 的函数。
- 含义：这是第 2 点和第 3 点的结合。它把函数图像中最底部的“平底”部分拉宽了。
- 最低点区间 \([min\_pos_L, min\_pos_R]\) 变成了 \([min\_pos_L + l, min\_pos_R + r]\)。
- 左边的拐点向右移 \(l\)，右边的拐点向右移 \(r\)。
- 操作：
lazy_L += l;lazy_R += r;- 这个操作非常强大，常见于这就好比把 \(f(x)\) 的那个“碗底”给拽宽了。
5. \((\min, +)\) 卷积 (Infimal Convolution)
公式： \(g(x) = \min_{y} (f(y) + h(x-y))\)
- 几何含义（Minkowski Sum）：
如果 \(f\) 和 \(h\) 都是凸函数，这个操作等价于几何上的 闵可夫斯基和。
直观地说，就是把两个函数的线段按斜率大小归并排序重新拼起来。- 例如：\(f\) 有一段斜率为 1 长度为 2 的线段，\(h\) 有一段斜率为 1 长度为 3 的线段，那么 \(g\) 会有一段斜率为 1 长度为 5 的线段。
- 常见特例：
如果 \(h(x) = k|x|\) (即斜率为 \(\pm k\))，这相当于限制了转移的“速度”。它会让 \(f(x)\) 图像中斜率绝对值 \(> k\) 的部分被“切掉”或者说被斜率 \(k\) 的直线替代。
6. 函数合并 (Function Merge)
公式： \(g(x) = f(x) + p(x)\) （其中 \(f\) 和 \(p\) 都是维护好的复杂凸函数）
- 场景：树上 DP，将子树的 DP 状态合并到父节点。
- 几何含义：两个凸函数的叠加。其拐点集合基本上是两个原函数拐点集合的并集。
- 操作：
- 启发式合并 (Small-to-Large)：将较小的堆中的元素暴力
pop出来push到较大的堆中。复杂度 \(O(N \log^2 N)\)。 - 可并堆 (Leftist Tree / Skew Heap)：直接在 \(O(\log N)\) 时间内合并两个堆。这是处理 Tree DP + Slope Trick 的标准做法。
- 启发式合并 (Small-to-Large)：将较小的堆中的元素暴力
7. 限制定义域 (Domain Restriction)
公式： 强制 \(x \in [L, R]\)，否则 \(f(x) = \infty\)。
- 几何含义：在 \(x=L\) 左侧和 \(x=R\) 右侧加上近乎垂直的“墙”。
- 操作：
- 向左堆 \(L\) 中插入无穷多个 \(L\)（或者是需要的最大斜率数量）。
- 向右堆 \(R\) 中插入无穷多个 \(R\)。
- 这会使得越过边界后的斜率迅速变得极大，从而在求最值时被排除。
8. 翻转 (Reflection)
公式： \(g(x) = f(-x)\)
- 含义：图像沿 Y 轴翻转。
- 操作：
- 交换左堆 \(L\) 和右堆 \(R\)。
- 堆内的值取相反数（因为 \(x\) 变为了 \(-x\)）。
- 这通常需要堆支持打“乘法标记”或者 Lazy Tag 配合交换指针。
总结表
| 数学操作 | 对应 DP 意义 | Slope Trick (双堆) 操作 |
|---|---|---|
| $+ | x-a | $ |
| \(f(x-c)\) | 转移代价：常数位移 | lazy_L += c; lazy_R += c; |
| \(\min_{y \le x} f(y)\) | 只要前面的最优解 | 清空右堆 \(R\) (或 R 只保留最小值点) |
| \(\min_{x-r \le y \le x-l} f(y)\) | 滑动窗口转移 | lazy_L += l; lazy_R += r; |
| \(f(x) + g(x)\) | 树上子节点合并 | 启发式合并堆 或 使用左偏树 |
| \(x \in [L, R]\) | 加上边界墙 | 插入多个 \(L\) 到左堆，多个 \(R\) 到右堆 |
理解这些操作后，你就可以像搭积木一样，把复杂的 DP 方程分解成这些基本操作，然后用 Slope Trick 的模板“翻译”成代码。