斜率优化-526互联

重点讲讲斜率优化的套路。
首先需要将式子化为 \(y=kx+b\) 的形式，其中 \(y,x\) 为一个关于变量 \(j\) 的式子，\(k\) 为一个关于常量 \(i,b\) 的式子。然后根据 \(x,k\) 的单调性考虑是二分还是直接单调。注意如果求最小值是下凸包，最大值是上凸包（最小值是直线从下面往上靠，最大值反之），然后如果删除队首不合法的，最小值和最大值也要反着来。可以自己用一个坐标轴上画一些点，用一条直线来靠就能回忆起来。