这篇博客主要讲述了决策单调性优化、斜率优化的原理及各自的实现方法，以及一些细节。
它们加上普通的单调队列优化，都是用来优化特殊的 $\rm DP$ 的转移方程的。不过适用范围不同。
一些定义
我们经常要做一些线性的动态规划问题，它的转移方程一般是这样的
$$f(i)=\min/\max{f(j)+w(j,i)}$$
我们称这种形式的 $\rm DP$ 为 $\rm 1D/1D$ 动态规划。
所谓 1D/1D 动态规划，指的是状态数为 $O(n)$，每一个状态决策量为 $O(n)$ 的动态规划方程。（状态一维，转移一维）
直接求解的时间复杂度为 $O(n^2)$，但是，绝大多数这样的方程通过合理的组织与优化都是可以优化到 $O(n\log n)$ 乃至 $O(n)$ 的时间复杂度的。
若 $f(j)$ 可以转移到 $f(i)$ ，那么我们称 $j$ 是 $i$ 的决策点。
若 $f(j)$ 可以转移到 $f(i)$ 且最优，那么我们称此时的 $j$ 是 $i$ 的 最优决策点。
决策单调
定义
1D1D动态规划：从左往右转移的时候，每个 $i$ 的最优决策点 $p(i)$ 一般是乱序的，没有什么规律。但是有时候我们发现当 $i$ 往右移到 $i+1$ 的时候，最优决策点 $p(i+1)$ 也在 $p(i)$ 的右边，相当于也往右移动了。这个时候我们就说决策满足单调性。
数学一点地说，设 $p(i)$ 是 $i$ 的决策点，有
$$\forall a\leq b,p(a)\leq p(b).$$
四边形不等式
有时候，我们可以根据不同的题目具体分析，即证
$$\forall a<p(i)<b,i<j,f(a)+w(a,j)>f(b)+w(b,j)$$
可以快速判断它是否满足决策单调，若
$$\forall a\leq b\leq c\leq d,w(a,d)+w(b,c)\geq w(a,c)+w(b,d)$$
那么这个 $\rm DP$ 满足决策单调性，这个用于判断的不等式称为四边形不等式。
记忆：包含转移不优于交叉转移
可以感性理解：包含转移意味着不满足决策单调，交叉转移意味着满足决策单调。
证明
具体证明就是考虑如何将这个四边形不等式转化为一开始的定义式。
假设 $f(c)$ 从 $b$ 转移过来，就有
$$f(a)+w(a,c)\ge f(b)+w(b,c)$$
两个式子相加
$$[f(a)+w(a,c)]+[w(a,d)+w(b,c)]\ge [f(b)+w(b,c)]+[w(a,c)+w(b,d)]$$
消去相同项
$$f(a)+w(a,d)\ge f(b)+w(b,d)$$
得证。
具体应用
有时候四边形不等式不是很好证。有一种思路是，不整体考虑，考虑拆分贡献，看其中的某一种情况会贡献给两边多少，然后合在一起。
例题： 证明区间内逆序对满足决策单调。
例如有这么一段区间：$ \mathop{|}\limits_{a} \dots A\dots \mathop{|}\limits_{b} \dots B\dots \mathop{|}\limits_{c} \dots C\dots \mathop{|}\limits_{d}$（每个大写字母表示这个区间）
我们要证明的就是 $\rm w(ABC)+w(B)\ge w(AB)+w(BC)$。对于每个逆序对 $(x,y)$，我们看它们在不同的区间内时，会贡献给哪些区间：
$x$ 所在区间 $y$ 所在区间 贡献情况 $\rm A$ $\rm A$ $1+0=1+0$ $\rm A$ $\rm B$ $1+0=1+0$ $\rm A$ $\rm C$ $1+0>0+0$ $\rm B$ $\rm B$ $1+1=1+1$ $\rm B$ $\rm C$ $1+0=0+1$ $\rm C$ $\rm C$ $1+0=0+1$ 我们发现在 $x\in A,y\in C$ 的时候左边的贡献大于右边的贡献。因此在任何情况下，交叉转移的代价总是不高于交叉转移的代价，所以满足决策单调性。
接下来是一些实现方法。
二分单调栈
不妨反过来想，每一个 $i$ 的最优决策点 $j$ 是单调的，那么每个最优决策点 $j$ 所对应转移到的 $i$ 的区间也是单调的。
那么我们可以用单调栈维护每一个 $j$，并记录它可以被最优决策到的最左边的点 $l(j)$，那么 $j$ 可以转移到的区间是 $[l(j),l(j+1)-1]$，最后一个最优决策点 $j$ 可以转移到的区间是 $[l(j),n]$。
有两种操作（这里记 $q[L]$ 为队首，$q[R]$ 为队尾）：
- 询问 $i$ 的最优决策点：不断取出队首，如果队首的区间没有包含 $i$（$l(q[L+1])\leq i$），就说明队首已经把它能转移到的点都转移了，于是我们把队首弹出。
- 插入一个决策点 $i$，找到它能转移的区间：分两步做。
- 不断取出队尾，如果队尾能转移到的最左边的点 $l(q[R])$ 的代价 $w(q[R],l(q[R]))$ 都不比 $i$ 转移代价 $w(i,l(q[R]))$ 优，那么可以直接弹出队尾，此时 $i$ 就把队尾的区间给吞并掉了；
- 搞定了全部吞并的，接下来的队尾可能还有右边的一些区间可以被 $i$ 吞并，于是可以二分区间 $[l(q[R]),n]$，找到一个最小的 $k$ 使得 $w(q[R],k)\geq w(i,k)$。然后把区间分裂，令 $l(i)=k$ 并加入队尾。
类比：和普通单调队列很像，只是多了一个转移区间的维护（二分）。
时间复杂度 $O(n\log n)$。（二分）
分治解决分层类 $\rm DP$
有时候的二维 $\rm DP$ 同一层的转移只与上一层有关，然后我们又发现它有时又满足决策单调性。当然这种情况也可以使用二分单调栈，但我们还可以用分治的思想。
定义 $solve(i,l,r,pl,pr)$ 表示现在做到第 $i$ 层 $\rm DP$，现在要算 $f(i,l)$ 到 $f(i,r)$的值，现在已经确定这一段区间的决策点区间在 $[pl,pr]$ 之间。
- 令 $mid=\dfrac{l+r}{2}$，暴力在 $[pl,\min(pr,mid-1)]$ 之间找 $f(i,mid)$ 的决策点 $f(i-1,pmid)$，可以算出 $f(i,mid)$。
- 于是因为它满足决策单调，所以区间 $[l,mid-1]$ 的决策点区间必定为 $[pl,pmid]$，区间 $[mid+1,r]$ 的决策点区间在 $[pmid,pr]$ 之间。
- 这显然是个子问题：递归 $solve(l,mid-1,pl,pmid)$ 和 $solve(mid+1,r,pmid,pr)$ 求解。
- 递归结束条件：$l>r$ 或 $pl>pr$。总问题：$solve(i,1,n,1,n)$。
十分奇妙。不过看起来复杂度有点假（？）但是它的复杂度的确是 $O(nm\log n)$。比正常的 $O(n^2m)$ 优。
证明： 因为每一层的决策点区间都是上一层切成的两段，所以每一次必定都是连续的，因此每一层决策点区间的总和长度都为 $O(n)$，然后因为递归层数不超过 $O(\log n)$ 层，于是每一次转移都为 $O(n\log n)$。
相似地，这种分层类二维 $\rm DP$ 称为 2D/1D 动态规划。
莫队双指针思想
有时候，计算代价 $w(j,i)$ 并不是能够 $O(1)$ 算出。但是，如果我们已经知道区间的代价 $w(j,i)$，且区间往外拓展or往内收缩 $1$ 个单位可以 $O(1)$ 求出。我们可以利用像莫队一样的东西，搞两个指针，表示现在的当前区间，然后如果要转移到目标区间，我们可以一个指针一个指针移动。
方法（四步记忆）：左右往外，左右往内。
分治做法可以这样做，但是单调栈不能（这就是为什么前面要连续介绍两种一维 dp 的做法）。因为二分的时候区间跨度很大，区间转移会被搞成 $O(n)$。但是分治只需暴力找决策点，贡献可以伸缩来算。
例题：CF868F Yet Another Minimization Problem（分治+莫队双指针）
$\rm cdq$ 套分治
前面 $\rm 2D/1D$ 可以用分治解决，如果贡献不能 $O(1)$ 求出那么就拿莫队来套。如果是一维的决策单调 $\rm DP$ 能不能解决呢？可以用 $\rm cdq$ 套着算。在函数 $\rm cdq(L,R)$ 中的流程：
- $\rm cdq(L,mid)$ ： 先把左半边的东西先算好；
- $\rm solve(L,mid,mid+1,R)$ ：计算左半边对右半边的贡献（和普通的分层 $\rm DP$ 类似）；
- $\rm cdq(mid+1,R)$ ： 再把右半边的东西先算好；
代价是多了一个 $\log$。
例题：求序列分段内逆序对数目之和最小值。
总结
- 一维 + 贡献快速算出 $\rightarrow$ 二分单调栈
- 一维 + 贡献伸缩计算 $\rightarrow$ $\rm cdq$ + 分层 + 莫队
- 二维 + 贡献快速算出 $\rightarrow$ 二分单调栈 / 分层
- 二维 + 贡献伸缩计算 $\rightarrow$ 分层 + 莫队
区间 $\rm dp$ 里的四边形不等式
在形如 石子合并 的区间 $\rm DP$ 中，我们会遇到这样的转移方程
$$f(i,j)=\min_{k=i}^j f(i,k)+f(k+1,j)+w(i,j)$$
注意，$w(i,j)$ 不和 $k$ 有关，如果有关，可以把它的贡献放到下一层再算。
相似地，如果
$$\forall a\leq b\leq c\leq d,w(a,d)+w(b,c)\geq w(a,c)+w(b,d)$$
那么它也满足决策单调，不过这个有点特别，我们可以求得 $f(i,j)$ 的最优决策点 $p_{i,j}$ 区间：
$$p_{i,j-1}\leq p_{i,j}\leq p_{i+1,j}$$
不过我们也可以感性理解：如果 $j\to j-1$，最优决策点应该也往左；如果 $i\to i+1$，最优决策点应该往右。于是应该在两个最佳决策点之间。
我们发现这样的话枚举 $k$ 的总体时间复杂度是可以降到 $O(n)$ 的（对于每一层）。
证明： 假设已经做完所有长度为 $l$ 的区间 $f(i,i+l-1)$，它们的决策点分别为 $p_i$。接下来要根据这些转移到所有长度为 $l+1$ 的区间，那么枚举 $k$ 时，每次枚举的区间分别为 $[p_1,p_2],[p_2,p_3],\dots,[p_{n-1},p_n]$，显然长度总和为 $O(n)$。
类比：和上面分治的时间复杂度证法差不多。
斜率优化
引入
单调队列（栈）给我们展现出了一种思想：在保证正确性的前提下，及时排除不可能的决策点，保持决策集合内部的有序性和查找决策的高效性。
其实质是优化 “决策”。
事实上，所有用到了单调队列优化的 $\rm DP$ 一般都满足决策单调。因为队首一直在弹出，也就意味着决策点在一直向后移动。
定义
对于动态规划
$$f(i)=\min/\max{f(j)+w(j,i)}$$
如果 $w(j,i)$ 内的式子只与 $i$ 有关 或者 只与 $j$ 有关（记 $w(j,i)=p(i)+q(j)+C$，$C$ 为常数项），那么这个式子可以转化成
$$f(i)=\min/\max{f(j)+q(j)}+p(i)+C$$
很明显，可以使用单调队列优化。
但是如果 $w(i,j)$ 里面有同时和 $i,j$ 有关的东西，这种方法就捉襟见肘了。那么斜率优化要搞定的，就是将 $w(j,i)$ 拆开后，存在同时包含 $i$和 $j$ 的乘积项的式子。
即我们要优化这样一个东西：
$$f(i)=\min/\max{f(j)+a(i)·b(j)+q(j)}+p(i)+C$$
转化式子
斜率优化的核心就是要把这个式子转化成 $\rm Y=KX+B$ （直线）的形式。
为了方便先去掉 $\min/\max$。我们把只含 $j$ 的项移到等式左边，其他移到右边，整理可得
$$f(j)+q(j)=-a(i)b(j)+f(i)-p(i)-C$$
然后将
- $f(j)+q(j)$ 视作 $\rm Y$；
- $-a(i)$ 视作 $\rm K$，$b(j)$ 视作 $\rm X$；
- $f(i)-p(i)-C$ 视作 $\rm B$。
所以每一个点 $(b(j),f(j)+q(j))$ 代入这个式子都能解出一个截距。要使 $f(i)\to \min/\max$，即是使得截距 $\rm B$ 取到最值。
把这些点搬到二维平面上，我们发现斜率 ${\rm K}=-a(i)$ 是个常量。也就是说，有一条斜率固定的直线在上下平移，尝试经过一个点使得截距取最值。
我们需要维护一个上/下凸壳（从此开始，如果没有特别说明，讨论的都是上凸壳），显然上凸壳下方的点都肯定不会比凸壳上的点优。排除了不可能的决策点。
凸壳的性质：上凸壳斜率单调递减，下凸壳斜率单调递增。（显然）
接着，我们来讨论凸壳上的这些决策点哪个最优。见上图，明显是那条直线作为凸壳的切线时的切点。这个切线的斜率和它的切点两边的斜率有一定关系。如图，若记这一条切线为 $l$，斜率为 $k_l={\rm K}$，切点为 $\rm B$，两边分别为 $\rm AB$ 和 $\rm BC$。有
$$k_{\rm AB}\geq {\rm K}\geq k_{\rm BC}$$
显然。同理，下凸壳反之。
也就是说，我们需要找到一个切点，使得它左边的斜率比 $\rm K$ 小，右边的斜率比 $\rm K$ 大。
针对不同的情况，我们有不同的实现方法。一般以两个性质来决定：
- 插入的坐标 横坐标 $x_i$ 递增；
- 询问的斜率 单调递增/减。
单调队列（满足性质1.2.）
用一个单调队列，维护凸壳上所有的点。
很多时候，方程中 ${\rm K}=-a(i)$ 总是单调递增/减的（例如前缀和之类）。换句话说，我们找到的切点也必定是单调向右的，而前面的凸壳的点肯定不会成为最优决策点，于是我们考虑把这些无用的决策点弹出。
插入的横坐标单调，意味着新加入的点只能从右边加入。考虑凸壳上最右边的两个点 $\rm P,Q$，和要插入的点 $\rm A$。如果 $k_{\rm PQ}\leq k_{\rm QA}$（想象一下就知道了），那么将 $\rm Q$ 弹出。
然后再将 $\rm A$ 加入凸壳。
教你学数学：两点 $\rm P,Q$ 斜率 $k=\dfrac{y_{\rm P}-y_{\rm Q}}{x_{\rm P}-x_{\rm Q}}$.
为了避免精度误差，可以交叉相乘比较大小。
例题：LuoguP3628 [APIO2010]特别行动队，LuoguP5017 摆渡车
二分+单调栈（满足性质1.）
如果 ${\rm K}=-a(i)$ 不单调，那么这个队列就不能把之前的点给弹出。有可能后面的询问又要用到前面的点……所以只能在队内二分。因为没有对队首的操作，单调队列成了单调栈。
时间复杂度 $O(n\log n)$。
$\rm CDQ$ 分治 / 平衡树（什么都不满足）
一个离线一个在线。
$\rm CDQ$ 分治：先按时间排序。然后对这个序列按横坐标 $x$ 排序，两边排序完后，两边都是 $x_i$ 递增，左半边时间比右半边早。 计算左半边对右半边贡献时，用单调队列。先按左边的点建一个凸壳，然后右半边一个个弹出算切点。
平衡树：支持前驱后驱的查找。
时间复杂度 $O(n\log n)$。
斜率优化的本质 $\rightarrow$ 维护凸壳
另外，由于凸壳相当于随时插入一条直线，因此也可以直接抛弃斜率优化的做法，直接使用李超线段树！
总结
- 插入单调 + 询问单调 $\rightarrow$ 单调队列
- 插入单调 + 询问随机 $\rightarrow$ 二分 + 单调栈
- 插入随机 + 询问随机 $\rightarrow$ $\rm cdq$ / 平衡树 / 李超线段树
值得注意的细节
- 判断上下凸壳依据： 截距 $\rm B$ 中 $f(i)$ 的符号，和 $\min/\max$。一般 $\min$ 为下凸壳，$\max$ 为上凸壳。
- 注意当计算斜率 $k=\dfrac{y_{\rm P}-y_{\rm Q}}{x_{\rm P}-x_{\rm Q}}$ 时，若 $x_{\rm P}=x_{\rm Q}$，要根据题目具体要求和 $y_{\rm P}-y_{\rm Q}$ 正负判断要返回什么。（如 LuoguP5017 摆渡车）
- 队列初始化大多都要先有一个点 $f(0)$，因为都要从 $f(0)$ 转移过来；
- 可能有一些点暂时不能加入凸包，如 LuoguP5017 摆渡车 的 $j\leq i-M$ 限制。可以搞一个当前加入指针 $r$，然后每次判断能否加入凸包。