单调性的应用

斜率优化

通常是维护一个一阶导单调递增/递减的序列，单调队列的最后一个元素即为最优解

凸壳

已知$x_i,b_i$，每次询问给定一个$k(k>0)$，对于$y_i=kx_i+b_i$，求使得$y_i$最大的$i$

首先，直觉告诉我们，如果$i<j$且$x_i<x_j,b_i<b_j$，那么$i$一定不是最优解，可以把$i$去掉

接下来我们考虑3条直线之间的关系

例题 Codeforces 573E

分块，并对每一个块维护一个凸包，遇到要更新的块，直接暴力重建凸包