（说是斜率优化，其实和斜率几乎没有关系）
（e…更新后确实有关系）
其实斜率优化和决策二分栈（队列）很像，下面分几种类型来讲。
一维斜率优化
针对形如 $d_i=\min\limits_{j=0}^{i-1} \big( d_j+w(j+1,i) \big)$ 的方程，而且需要满足决策单调性。
此处重新说一下，如果我们发现一个转移点 $x$ 在 $d_i$ 的时候已经比另外一个转移点 $y$ 要更优了（$x>y$），那么转移点 $y$ 在后面（$d_{i+1}$ 及以后）就不可能比转移点 $x$ 要更优了，那么这个DP一定满足决策单调性，而且反过来也一样（见"决策单调性.md"）。
其实证明是否满足单调性只用看：如果一个决策点 $x$ 如果在 $d_i$ 的转移中已经比决策点 $y$ 要优了，那么 $d_{i+1}$ 中是否仍然满足这个条件。
证明了满足决策单调性后，就可以开始斜率优化了。
我们首先要考虑推斜率式：
其实斜率式就是把式子 $d_x+w(x+1,i)<d_y+w(y+1,i)$（$x>y$）不断移项、变化，直到式子左边只和 $x$、$y$ 有关，右边只和 $i$ 有关为止。
此时的斜率式一般左边是个分数，而且这个分数还需要把分子和分母的下标对应：
如果斜率式最后是像这样的：
$\dfrac{d_x-d_y}{v_y-v_x}>-a_i$
那么就不是个合法的斜率式，需要变成：
$\dfrac{d_x-d_y}{v_x-v_y}<a_i$
才是合法的。
注意，这里说的是“合法的”，而不是“正确的”，其实最上方的斜率式也可以使用，就是不能叫“斜率式”了（斜率的公式是 $\dfrac{y_2-y_1}{x_2-x_1}$）。
设此时的斜率式就是上面说的：
$\dfrac{d_x-d_y}{v_x-v_y}<a_i$
那么，我们就定义 $\text{slope}(y,x)=\dfrac{d_x-d_y}{v_x-v_y}$。
有了上面函数，显然如果存在两个转移点 $x$ 和 $y$（$x>y$）在转移到 $d_i$ 的时候满足 $\text{slope}(x,y)<a_i$，那么就说明转移点 $x$ 比转移点 $y$ 更优，转移点 $y$ 在后面就不需要了。
下面默认推出来的斜率式就是上式，并默认 $a$ 数组单调不降。
upd：其实上面决策单调性的证明并不需要非常复杂地证明，其实只要证明斜率式的右项是否单调即可，即如果中间符号是小于，只用证明右项是否单调递增，反之亦然。（23.1.8）
我们维护一个单调队列 $q$（设队头下标为 $h$，队尾下标为 $t$）代表目前还没有被淘汰的那些转移点，然后考虑转移 $d_i$：
- 首先，如果队列大小大于等于 $2$ 且 $\text{slope}(q_h,q_{h+1})<a_i$，那么就直接弹出队首。
有人问，根据单调队列性质，$q_h<q_{h+1}$，那不是和上面的假设 $j>k$ 冲突了吗？那直接弹出 $q_h$ 岂不是会错？答案是否定的。
首先，显然，对于所有的 $(j,k)$，都满足 $\text{slope}(j,k)=\text{slope}(k,j)$。
有了上述性质，即 $\text{slope}(q_h,q_{h+1})=\text{slope}(q_{h+1},q_h)$，那么就和假设不冲突了。
所以，如果 $\text{slope}(q_{h+1},q_h)<a_i$，那么由于 $q_{h+1}>q_h$，所以 $q_h$ 就会被 $q_{h+1}$ 所取代，就会被弹出队列。
- 其次，以 $q_h$ 作为转移点转移 $d_i$。
- 然后，如果队列大小大于等于 $2$ 且 $\text{slope}(q_{t-1},q_t) \geq \text{slope}(q_t,i)$，那么就直接弹出队尾。
首先，在此时的 $q_t$ 和 $i$ 在将来成为队列的前两个元素的时候，且 $\text{slope}(q_h,q_{h+1})<a_i$ 的条件也满足的时候（此时的时刻设为时刻1），此时的 $q_t$ 也会被弹出。
其次，在此时的 $q_{t-1}$ 和 $q_t$ 在将来成为队列的前两个元素的时候，且 $\text{slope}(q_h,q_{h+1})<a_i$ 的条件也满足的时候（此时的时刻设为时刻2），此时的 $q_{t-1}$ 也会被弹出。
显然，时刻1小于时刻2。
所以综上所述，如果此时的 $q_{t-1}$ 被弹出了，那么 $q_t$ 也被弹出了，而 $q_{t-1}$ 更靠队头一些，所以 $q_t$ 是不需要的。
- 最后，在队尾加入 $i$。
二维斜率优化
其实也差不多，它针对的是形如 $d_{i,j}=\min\limits_{k=0}^{i-1} \big( d_{k,j-1}+w(k+1,i) \big)$ 的转移方程，且满足决策单调性（记 $d_{i,j}$ 的最优转移点为 $f_{i,j}$，那么此处的“决策单调性”就是指的对于所有的 $i$、$j$ 都满足 $f_{i,j} \leq f_{i+1,j}$）。
实现也差不多，我们直接从小到大枚举 $j$，然后对于所有 $i$ 分别用上述做法转移即可，就是需要改一些细节，但也不多。
（参考题目：M2515）
没有决策单调性的斜率优化（upd on 23.1.6）
针对形如 $d_i=\max\limits_{j=0}^{i-1} \big( d_j+w(j+1,i) \big)$ 的方程，但不满足决策单调性。
还是老规矩，我们推导一下斜率式，设推导结果为 $\dfrac{y_j-y_k}{x_j-x_k}>s_i$，并且要求 $x$ 数组单调不降，但 $s$ 数组不一定，可能是非常不规则的数组。
此处可以发现我们变换了一下变量名，其实没有决策单调性的斜率优化我就是用「把一个转移点 $j$ 想成一个二维平面上的坐标 $(x_j,y_j)$」的方法理解的。
一样，我们维护一个单调队列 $q$（设队头下标为 $h$，队尾下标为 $t$）代表目前还没有被淘汰的那些转移点（当前队列内的点斜率单调递减），然后考虑转移 $d_i$：
- 首先，由于不满足单调性，所以此处不能弹出队首，我们需要二分出斜率小于等于 $s_i$ 的最后面的下标来作为转移点。
- 其次，以找到的下标为转移点来转移 $d_i$。
- 然后，如果队列大小大于等于 $2$ 且 $\text{slope}(q_{t-1},q_t) \leq \text{slope}(q_t,i)$，那么就直接弹出队尾。
有人对这个过程有疑问，此处解释一下。
其实这个单调队列里维护的是一个斜率单调递减的凸包（不要和数学知识里的“凸包”搞混了，和那个“凸包”没有任何关系；下面的“凸壳”也是指的“凸包”），如下图所示：
在这里，“凸包”其实就是指的如上图的一个“包”住所有点的“拼合线段”（多个线段“拼”起来后的东西在这里称为“拼合线段”）。
我们考虑新加一个点：（最右上角）
比较此时队列后两个元素：
显然两个绿色虚线相比，前者斜率小于后者，所以弹出队尾，继续比较：
还是前者（斜率）小于后者，弹出队尾，继续比较：
终于满足条件了，所以队列最后只剩下这些元素了：
自己推一下式子就知道了，其实上面那个斜率式原本的形式是 $y_j-s_i \times x_j>y_k-s_i \times x_k$（即 $w(j+1,i)=y_j-s_i \times x_j$），回顾整个删除过程，显然所有删除的点都不可能比最后留下的三个转移点要更优。
其他情况可以自己讨论一下，很容易证明。
- 最后，在队尾加入 $i$。
（参考代码：M2484）
X坐标不满足递增的斜率优化（upd on 23.2.26）
针对形如 $d_i=\max\limits_{j=0}^{i-1} \big( d_j+w(j+1,i) \big)$ 的方程，但推导后的斜率式中X坐标不满足决策单调性。
还是老规矩，我们推导一下斜率式，设推导结果为 $\dfrac{y_j-y_k}{x_j-x_k}>s_i$，并且假设 $x$ 数组（X坐标）并不单调，但 $s$ 数组不一定，可能是非常不规则的数组。
（注意，X、Y坐标不一定是一开始就能知道的，可能需要在求出DP值后才可以求出的，但 $s$ 数组必须在一开头就能求出）
初始化
在这种情况下，我们就要用到CDQ分治了。
我们直接给 $d$ 数组赋初值，并记录初始每个点的X坐标和Y坐标（还有下标），赋值到一个数组 $q$ 里去，然后把 $q$ 数组按 $s_i$ 从大到小排序。
设计CDQ函数
然后我们考虑设计 $\text{cdq}(l,r)$ 函数。
首先，如果 $l=r$，那么此时 $d_l$ 的值就知道了，所以我们就用新的 $d_l$ 值重新更新 $q_l$ 的X、Y坐标。
否则，我们求出 $[l,r]$ 区间的中点 $\text{mid}$。
然后，我们把 $q_l \sim q_r$ 内所有的 $q_i$ 按照其原本下标值（设为 $q_i . \text{id}$）分组：把满足 $q_i . \text{id} \leq \text{mid}$ 的分成一组，依次赋值到 $q_l \sim q_{\text{mid}}$；另一部分，即满足 $q_i . \text{id}>\text{mid}$ 的分成一组，依次赋值到 $q_{\text{mid}+1} \sim q_r$。
由于我们在下面计算时，需要用到 $q_l \sim q_{\text{mid}}$ 的真实X、Y坐标，所以要先递归 $\text{cdq}(l,\text{mid})$。
然后，我们考虑 $d_l \sim d_{\text{mid}}$ 对 $d_{\text{mid}+1} \sim d_r$ 的影响。
我们先对 $d_l \sim d_{\text{mid}}$ 用上述方式（斜率优化模板）建一个凸壳，用一个队列 $\text{que}_{h \dots t}$（名称为 $\text{que}$，队首下标为 $h$，队尾下标为 $t$）存起来。
我们再循环 $i=\text{mid}+1 \sim r$，然后看如果 $q_h$ 比 $q_{h+1}$ 要劣，删除 $q_h$。
弹出所有无用状态后，直接用 $q_h$ 更新 $d_i$ 即可。
执行完转移后，递归 $\text{cdq}(\text{mid}+1,r)$。
但要注意，可以维护凸壳有且仅当X坐标递增，所以此处要拿 $l \sim \text{mid}$ 和 $\text{mid}+1 \sim r$ 的排序结果，把 $q_l \sim q_r$ 内所有元素按X坐标递增顺序排序。
（参考代码：M2590）
补充：
名不副实的意思是：空有虚名，名声和实际不一致。也说名不符实。