斜率优化笔记

首先看到有 \(i, j\) 无法分离的项的 \(\rm DP\) 一般就是斜率优化，像 \((s_i - s_j)^2\) 之类的。

首先将转移方程式写成 \(b_i = y_j - k_ix_j\) 的形式，拍到坐标系上。那么等价于用斜率为 \(k_i\) 的直线去切点，第一个切到的点是哪个，即截距最小/最大。显然切到的点在凸包上，即找到第一个凸包上的点 \(q_i\) 满足 \(slope(q_{i - 1}, q_i) \le k \le slope(q_{i}, q_{i + 1})\) 优化方式如下：

• 如果 \(x, y\) 都单调递增，那么可以直接在 \(\rm DP\) 过程中用单调队列维护一下凸包， \(O(n)\)。

• 如果 \(x\) 递增的话，可以使用二分队列，\(O(n \log n)\)。

• 否则 \(\rm CDQ\) 分治 或 平衡树（不推荐），\(O(n \log ^2 n)\)。

但是还有最简单粗暴的方法：即把转移方程式表示成 \(y_j = k_j x_i + b_j\) 这样直线的形式。然后使用李超线段树优化，因为是全局加直线不用分拆区间，离散化 \(x\) 即可做到 \(O(n \log n)\)，码量小常数小，还不用动脑子，严格偏序 \(\rm CDQ\) 和平衡树（当然平衡树维护凸包还是很有必要学的）。