斜率优化

斜率优化就是说如果当前的最优解同时取决于之前的所有点处的最优解，同时它与当前点的某个性质呈一次函数关系，这样当前点的最优解就是斜率固定的直线系的最大/小截距。这个截距一定在直线与上/下凸壳相切的时候取到。

所以斜率优化需要维护一个凸壳，然后在询问时：

• 如果斜率具有单调性，可以用单调队列实现；
• 如果斜率没有单调性，可以用二分。

NOTE

点 $(x_i,y_i)$ 的插入顺序必须保证 $x_i$ 单调，否则求出的凸壳是错误的。

IMPORTANT

易错点：

• 注意 $x_i$ 的插入顺序是 $x_i$ 递增还是递减；
• 注意二分时向量的方向应该是 $(1,k)$ 还是 $(-1,-k)$。