「NOI2014」购票 「树上斜率优化」
首先易得方程，且经过变换有
$$\begin{aligned} f_i &= \min\limits_{dist_i - lim_i \le dist_j} \{f_j + (dist_i - dist_j)p_i + q_i\} \\ f_j &= p_idist_j + f_i - dist_ip_i - q_i \end{aligned}$$
在一条直线上时，斜率优化可以用普通$CDQ$分治实现（会不会过于麻烦？），那么对于在树上斜率优化时，考虑点分治
这时就在点分治中运用$CDQ$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了
注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...
「NOI2007」货币兑换 「CDQ分治实现斜率优化」
首先每次买卖一定是在某天 $k$ 以当时的最大收入买入，再到第 $i$ 天卖出，那么易得方程：
$$f_i = \max \{\frac{A_iRate_kf_k}{A_kRate_k + B_k} + \frac{B_if_k}{A_kRate_k + B_k}\}$$
再令
$$\left\{\begin{aligned} x_k = \frac{Rate_kf_k}{A_kRate_k + B_k} \\ y_k = \frac{f_k}{A_kRate_k + B_k}\end{aligned}\right.$$
则有
$$\begin{aligned} f_i &= \max \{A_ix_k + B_iy_k\} \\ y_k &= - \frac{A_i}{B_i}x_k + \frac{f_i}{B_i} \end{aligned}$$
那么现在需要找到一个点 $(x_k, y_k)$ 使得直线的截距最大
由于斜率和横坐标皆不满足单调性，可以用平衡树等维护，这里使用CDQ分治实现
实现过程如下：
Ⅰ 将数据按照斜率$\frac{A_i}{B_i}$降序排 ...