二分和CDQ/Splay配合斜率优化

在我们回忆一下最基础的斜率优化模板题的过程：

1. 将初始状态入队。
2. 每次使用一条和$i$相关的直线$f(i)$去切维护的凸包，找到最优决策，更新$dp_i$。
3. 加入状态$dp_i$。如果一个状态（即凸包上的一个点）在$dp_i$加入后不再是凸包上的点，需要在$dp_i$加入前将其剔除。

二分/CDQ配合斜率优化分别是对步骤2和步骤3的实现进行一些修改以适应一些特殊情况。

二分+斜率优化

众所周知，当我们在$i$这个点寻找最优决策时，会使用一个和$i$相关的直线$f(i)$去切我们维护的凸包。切到的点即为最优决策。对于一个下凸包（上凸包同理），且$f(i)$的斜率随着$i$单调递增，如果队首的两个点斜率小于$f(i)$时，我们就可以把第一个点出队，因为第一个点以后都不可能成为最优决策了。这就是斜率优化模板题的思路。因为每个点只会被出队一次，所以复杂度是$O(n)$的。

但是对于有些问题，$f(i)$并不是递增的。所以我们需要保存凸包的每一个节点，然后每次用当前的直线去切这个凸包。这个过程显然可以使用二分解决，因为凸包上相邻两个点的斜率是有单调性的。

例题： Codeforces 1420E

CDQ/Splay+斜率优化

我们知道，在步骤3结束时，我们会向凸包中加入$dp_i$这个状态。在模板题中，这一点很好实现，因为状态点的横坐标$X(i)$是单调的，我们只需要把这个点插入到队尾即可。但是如果$X(i)$没有单调性，该如何实现？我们可以使用平衡树，实现凸包的动态维护，但是这样比较麻烦，我们考虑另外一种方法：CDQ分治。

斜率优化是为了快速寻找动态规划的最优决策点。如果我们使用状态集合$S$中的每个状态$dp_j, j\in S$去更新$dp_i$。只要最优决策点$k$满足$k\in S$，那么我们$dp_i$的决策就一定是最优的。

我们可以使用CDQ分治，CDQ(l,r)代表求$dp_i,i\in [l,r]$。对于CDQ(1,n)，我们先调用函数CDQ(1,mid)解决$dp_i,i\in[1,mid]$。然后我们对$[1,mid]$这个区间内的点建一个凸包，然后使用这个凸包去更新$dp_i,i\in [mid+1,n]$。

对于$[mid+1,n]$中的每个点，如果它的最优决策的位置是在$[1,mid]$这个区间，在这一步操作中他就会被更新成最优答案。当执行完这一步操作时，我们发现$[1,mid]$中的所有点已经发挥了全部的作用，凸包中他们存不存在已经不影响之后的答案更新。因此我们可以直接舍弃这个凸包，并使用CDQ(mid+1,n)解决右区间的问题。复杂度$n\log n$

例题：[NOI2007]货币兑换