小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：$A$ 纪念券（以下简称 $A$ 券）和 $B$ 纪念券（以下简称 $B$ 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：
（a）卖出金券：顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP%$ 的 $A$ 券和 $OP%$ 的 $B$ 券以当时的价值兑换为人民币；
（b）买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rate_K$ ；
注意到，同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。
例如，假定接下来 $3$ 天内的 $A_k$、$B_k$、$Rate_K$ 的变化分别为：
.png)
假定在第一天时，用户手中有 $100$ 元 人民币但是没有任何金券。用户可以执行以下的操作：
.png)
提示：
- 输入文件可能很大，请采用快速的读入方式。
- 必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币；每次卖出操作卖出所有的金券。
链接
题解
最优策略肯定是只有两种状态：全仓/空仓，然后每天我们只有若干种选择：全买，全卖，全买+全卖，啥都不做。
注意到我们可以 $dp$ …
先写暴力转移…注意到我们事实上只需要记录我们有多少钱，在哪天买入的话就会有多少的比例。
所以我们令 $dp[i]$ 为在第 $i$ 天拥有的最多钱，假设我们上次全部卖出+全部买入在第 $j$ 天，状态转移：
$$
dp[i] = \max\left(\max _ {j=1}^{i-1}(dp[j]\times \frac{r[j]*a[i] + b[i]}{r[j]*a[j]+b[j]}),dp[i-1]\right)
$$
很好理解嘛…就是一个决策在哪天全买/全卖的问题。
暴力转移可以拿到 $60$ 分…上古时代的暴力分还是很好拿的。
正解的话，需要我们深入挖掘这个式子。
我们先忽略最后一个不买不卖的情况，来继续看：
$$
dp[i] = \max _ {j=1}^{i-1}(dp[j]\times \frac{r[j]\cdot a[i] + b[i]}{r[j] \cdot a[j]+b[j]})
$$
对于给定的决策点 $j$ ，则有：
$$
dp[i] = dp[j] \times \frac{r[j]\cdot a[i] + b[i]}{r[j]\cdot a[j]+b[j]}\
dp[i] = (r[j]\cdot a[i] + b[i])\times \frac{dp[j]}{r[j]\cdot a[j]+b[j]}\
dp[i] = b[i]\times \frac{dp[j]}{r[j]\cdot a[j]+b[j]} + a[i] \times \frac{r[j]\cdot dp[j]}{r[j]\cdot a[j]+b[j]}
$$
如果我们令：
$$
x[j] = \frac{r[j]\cdot dp[j]}{r[j]*a[j]+b[j]}, y[j] = \frac{dp[j]}{r[j]\cdot a[j]+b[j]}
$$
那么式子就会变成：
$$
dp[i] = a[i] \times x[j] + b[i] \times y[j]
$$
略微变换：
$$
y[j] = - \frac{a[i]}{b[i]} \cdot x[j] + \frac{dp[i]}{b[i]}
$$
我们注意到，这里面的斜率仅与 $i$ 相关，$x,y$ 均只与 $j$ 相关，最后的截距下面除的是一个常数，那么只要截距最大， $dp[i]$ 就会最大。
而且，只要 $x[j]$ 和 $y[j]$ 一经确定，便不改变。
所以现在问题变成：支持插入点，查询某个给定斜率的直线且经过某个点，使得这条直线的截距最大。
在以往的斜率优化问题里面，我们一般有两个单调性：插入的点的 $x$ 坐标单调，直线的斜率单调。那么我们用单调队列就可以维护凸包，然而这里我们这两个性质全都没有，所以我们只能用更高级的东西，比如 $\text{CDQ}$ 分治，比如 $\text{Splay}$ 。
我用了 $\text{Splay}$ 来维护这个上凸包。
具体实现的话，就是需要处理两个问题：找到第一个斜率较给定值大的点，和插入一个点。
在 $\text{Splay}$ 上二分即可。最好是每个点代表这个点到前一个点的斜率。
先判断在不在凸包里，再根据x坐标插入，然后在向两边pop，维护凸包性质。注意pop的条件比较容易写错。
不知道为啥，BZOJ 上过不了。本地下下来数据、传到 luogu 上都可以过。
代码
| |
