深入理解斜率优化

转移到 \(i\) 时考虑两个转移点 \(j<k\) 中 \(j\) 更优的条件，可以写成 \(\dfrac{a_k-a_j}{b_k-b_j}\) 大于或者小于 \(c_i\) 的形式。

把信息看做二维平面上的点 \((b,a)\)，那么上面的条件实际上就是 \(j\) 与 \(k\) 两点间的斜率大于或者小于 \(c_i\)。

所以可以维护一个凸包，具体地，大于号维护下凸包，小于号维护上凸包。这样凸包内的点在任何情况下都是不优的，因为它左侧和右侧在凸包上的第一个点一定有一个是优于它的。

因为凸包上斜率单调，所以对于当前 \(c_i\)，最优转移点一定是第一个与后面的点斜率大于或者小于 \(c_i\) 的点。也就是用斜率为 \(\bm{c_i}\) 的直线去切这个凸包切到的那个点。

新加转移点的横坐标与寻找最优转移点的直线斜率均单调

用单调队列维护即可。

新加转移点的横坐标单调寻找最优转移点的直线斜率不单调

仍然用单调队列维护，只不过查询要二分。

新加转移点的横坐标与寻找最优转移点的直线斜率均不单调

无脑一点用平衡树动态维护凸包，有脑一点就写 CDQ 分治。