如果某天能够赚钱，那么一定会在这天把手上的金券全卖掉。同样如果某天要买，一定会把所有钱花光。
那么令\(f_i\)表示到第\(i\)天所拥有的最多钱数（此时手上没有任何金券），可以选择什么都不干，\(f_i=f_{i-1}\)；也可以从之前的某一天\(j\)花\(f_j\)的钱买金券，在第\(i\)天全卖掉。用第\(j\)天的信息算一下买了多少\(A,B\)，就可以得到第\(i\)天卖了多少钱。
所以有\(f_i=\max\{f_{i-1},\ A_i\frac{f_jk_j}{A_jk_j+B_j}+B_i\frac{f_j}{A_jk_j+B_j}\}\)。
把后面那部分写成直线的形式：\(\frac{f_i}{B_i}-\frac{A_i}{B_i}*\frac{f_jk_j}{A_jk_j+B_j}=\frac{f_j}{A_jk_j+B_j}\)，令\(x_j=\frac{A_i}{B_i}*\frac{f_jk_j}{A_jk_j+B_j},\ y_j=\frac{A_i}{B_i}*\frac{f_j}{A_jk_j+B_j}\)，\(\frac{f_i}{B_i}-\frac{A_i}{B_i}x_j=y_j\)。要求用\(k=-\frac{A_i}{B_i}\)的直线去切\((x_j,y_j)\)使得截距最大，也就是维护上凸壳。
但\(x\)即每个决策点不是单调的，就需要平衡树/CDQ分治去维护凸包。
CDQ分治：
先将所有点按斜率\(k\)排序。
先处理完左区间询问，然后将左区间按横坐标\(x\)归并排好序。这样处理右区间询问的时候（现在只考虑当前左区间对整个右区间询问的影响，也就是要对左区间维护上凸壳），左区间的\(x\)有序就可以直接用单调栈把上凸壳维护出来了。
而右区间已经按斜率\(k\)排好序了，所以可以\(O(n)\)在上凸壳中得到最优解（实现当前整个左区间对右区间的转移）。
当递归到\(l=r\)，就说明已经处理完该点\(l\)之前的点对\(l\)的影响了，就可以直接得到\(f_l\)的值（顺便要和\(f_{l-1}\)取\(\max\)）并更新\(l\)这个决策点的信息了。
平衡树：
节点按\(x\)排序。每个节点维护与左边点和右边点的斜率\(lk,rk\)。（树上的节点都是凸包上的，凸包内部的就不要了）
对于新的决策点\(x\)，直接先插入到平衡树中。
然后将\(x\)转到根。先找左边第一个能与\(x\)构成凸包的点：若当前点\(y\)与前一个点的斜率\(lk\gt k(x,y)\)，那么如果\(y\)右边还有在凸包上的点，就继续向右找（没有就结束）。否则若\(lk\lt k(x,y)\)，则应继续往左找。
找右边第一个能与\(x\)构成凸包的点同理。
最后，如果\(x\)就在凸包里面，即\(lk(x)<rk(x)\)，就要把\(x\)从平衡树中删掉。
查询就根据斜率直接查询最优决策点了。
CDQ分治：
Splay：（快好多啊）
BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)
原文：https://www.cnblogs.com/SovietPower/p/10111492.html