前置知识
斜率优化
引入
考虑以下问题：
在数轴上存在 \(n\) 个点，第 \(i\) 个点的横坐标为 \(x_i\)，将两个点连接的代价为 \((x_i-x_j)^2\)，求将点 \(1\) 和点 \(n\) 连接的最小代价，连接具有传递性。
我们容易发现这是一个 DP 问题，设 \(f_i\) 表示将点 \(1\) 与点 \(i\) 连接的最小代价，则有：
\(f_i=\min_{j<i} f_j+(x_i-x_j)^2\)
直接 DP 的时间复杂度是 \(O(n^2)\) 的，是否有什么优化方法？
斜率优化！
实现
我们将 DP 方程转化一下：
发现了什么？
如果我们设
那么 DP 方程就变成了 \(y=kx+b\)，这是一个我们无比熟悉的形式，也就是一次函数（直线）的解析式。
那么我们每得到一个 \(f\) 的值，就可以将其对应的 \(k,b\) 算出来，在李超线段树上插入一条直线，每次求 \(f\) 时，在线段树上查询其对应的 \(x\) 对应的所有 \(y\) 的最小值。
这样 DP 的时间复杂度就被优化到了 \(O(n\log n)\)。
- 是否存在更优做法？
如果说给定的点是按横坐标排好序的，也就是说横坐标单调递增，那么我们可以换一种优化方式得到更优的复杂度。
设
那么我们就得到 \(b=y-kx\)，其中，\(b\) 是未知的，而 \(y,k,x\) 均已知。
我们将每一个 \((x_j,f_j+x_j^2)\) 看作一个平面直角坐标系上的点，那么我们的问题就变成了下列形式：
已知一条直线的斜率，且这条直线经过平面上若干点中的一个，求该直线截距的最小值。
容易发现，这条直线经过的点一定在这些点的下凸壳上，且该直线的斜率比上一条直线大，比下一条直线小。
这个点被称为最优决策点，也就是我们 \(f\) 的转移点。
我们发现，\(x,k\) 都是单调的，这时，我们就可以用单调队列维护下凸壳，将 DP 的时间复杂度优化到 \(O(n)\)。
当然，若给出的点没有被排序好，我们可以自己排序，但时间复杂度就变成了 \(O(n\log n)\)。
概括
总的来说，斜率优化可以优化符合下列形式的 DP 转移时间复杂度：
其中，\(c_i,d_j\) 与 \(f\) 无关。
优化方式有很多种：
-
单调队列维护凸壳：要求 \(x,k\) 均单调，时间复杂度为 \(O(n)\)。
-
单调栈维护凸壳加二分：要求 \(x\) 单调，时间复杂度为 \(O(n\log n)\)。
-
李超线段树优化：没有要求，时间复杂度为 \(O(n\log n)\)。
-
平衡树动态维护凸包：没有要求，时间复杂度为 \(O(n\log n)\)。
-
CDQ 分治优化：没有要求，时间复杂度为 \(O(n\log ^2n)\)。
其中，除了李超线段树优化之外，其他方法均是将 \((d_j,b_j)\) 看成点，将 \(a_i,c_i\) 分别看成一条直线的截距和斜率，在已知斜率的条件下求截距的最值。
而李超线段树将 \(d_j,b_j\) 看成直线的斜率和截距，在已知横坐标的情况下求纵坐标的最值。