何为斜率优化
对于一类动态规划问题，方程式诸如
$$
f_i=\max\{c_i + k_i \cdot x_j + y_j | j \lt i\}
$$
朴素的 $dp$ 做法的时间复杂度是 $O(n^2)$ 的，可以利用这个方程的一些特殊性质达到 $O(n \text{log}n)$ 乃至 $O(n \text{log}^2n)$
从改写方程开始
$$
f_i=\max\{c_i + k_i \cdot x_j + y_j | j \lt i\}
$$
可以改写为
$$
-k_i \cdot x_j + f_i - c_i = y_j
$$
这个式子的意义是一条斜率为 $-k_i$ ，过点 $(x_j,y_j)$ ,截距为 $f_i-c_i$ 的直线
此时目标是最大化 $f_i - c_i$ ，由于 $c_i$ 是定值，原目标等价于最大化 $f_i$
维护点集和获取最大值
那么现在需要维护一个点集 $(x_j,y_j)$ ，每当处理完 $f_i$ 后就需要将 $(x_i,y_i)$ 加入点集
显然使得$f_i$取得最大值的点是在点集的凸壳上，所以要维护一个凸壳
查询使得$f_i$最大的点的时候，是用的一条斜率固定的直线去切这个凸壳，可以通过二分斜率或者凸壳上三分查询
常用的维护套路
加入的点的$x$递增，查询的斜率递增
这是最普通的斜率优化的形式
回忆静态凸壳的构造方法：按照$x$排序后依次添加并维护凸性
那么由于点的$x$递增，用这种方法维护就行
由于查询的斜率是递增的，那么相当于直线一直在某时针旋转，同时加入的点的$x$递增，显然决策递增，可以用单调队列维护
加入的点的$x$递增，查询的斜率不保证递增
点还是原先的加入方法就行，但是斜率不一定递增了
那么直接在凸壳上二分或三分就行了
加入的点的$x$不保证递增，查询的斜率递增
点的加入需要用std::set等进行维护了，查询的话也需要二分或三分了
$x$和斜率都不保证递增
二进制分组
维护log个凸壳，大小分别为$x,\frac{x}{2},\frac{x}{4},\cdots$（虽然这么表述有些不严谨，但是可以类似的意会一下），其中$x$表示最大的那个凸壳，这些用一个vector来存储，大小递减
当添加一个新的点后，放到vector的尾部，并比较最后两个凸壳的大小是否相等，相等的话就暴力弹出这两个凸壳并将它们暴力合并，合并完后再放入vector尾部
查询的话在每个凸壳上二分或三分即可
可以证明时间复杂度是$O(n \text{log}^2 n)$
cdq分治
嘛，这个就说来话长了
首先开一个结构体，记录一下$i,k_i$，分别表示计算第$i$个$f$（这里$i$表示$id$)，用到的斜率为$k_i$
然后按照$k_i$将结构体排序
定义cdq(l,r)表示计算所有$l \le i \le r$的$f_i$
那么执行完$cdq(1,n)$之后就完成任务咯
那么假设执行了cdq(l,r)，不妨先根据$mid=\lfloor \frac{l+r}{2} \rfloor$将下标为$[l,r]$的结构体分开计算
先把所有$id \le mid$的分成一波，另外的分成一波，这个操作要在原序列上进行
分割完之后，结构体的$[l,mid]$中的元素的$id$都是$\le mid$的，此时先递归一下cdq(l,mid)
假设cdq(l,mid)递归完之后，这些元素所表示的点集都已经排好序了
由于在最开始的时候已经按照$k_i$排序了，所以$[mid+1,r]$实际上斜率是递增的
那么用$[l,mid]$的点构建凸包后，只需要用单调队列扫一遍更新就好咯？因为这里用的$[l,mid]$中的点去更新的$[mid+1,r]$
更新完之后在调用一下cdq(mid+1,r)就完成任务咯？
不不不，别忘了需要保证计算完cdq(l,r)之后，$[l,r]$的点集已经排好序了
发现$[l,mid]$和$[mid+1,r]$分别都排好序了，那么归并排序一下就好咯？
时间复杂度$O(n \log n)$
也许看一下代码比较好理解
平衡树/std::set
二进制分组可以支持在线查询$f_i$，但是时间复杂度比较高
cdq分治可以支持复杂度较小的查询$f_i$,但是需要离线
如果强制在线的查询$f_i$呢？
用平衡树来维护凸壳，并在上面二分！
甚至你可以用std::set
