ARC072D Dam

题意：有个水库，最多能存 单位水，一开始是空的。

接下来 天，第 天早上有 单位的，水温为 的水流入水库。

每天晚上你可以放掉一些水，多少自定，但必须保证第二天水库不会溢出。

现在问，对于每个 ，在使用最优放水策略的情况下，第 天水库是满的情况下最高水温（每一问之间互相独立）。

，时限 。

---

总水温 各部分不同温度的水的 体积温度 的和除以总量 。

我们称 体积温度 为“热量”。由于体积 一定，我们只需要最大化热量。

记 表示第 天晚上，若水库内只能保留 升水，能获得的最大热量。

若将 视作函数 ，观察其性质。

若存在一组方案，容量为 ，热量为 ，则单纯的倒水可以得到 这个和原点相连的线段。

此外，水变多了热量不会变少。对于 ，。

于是，这个函数上的任意一点，向原点的连线下方不会有函数，水平向右发射的射线下方也不会有函数。不难发现，这必然是一个上凸壳。

接下来，考虑凸壳 的转移，如图 ：

转移无非两步，第一步强制加水，第二步任意倒水。第一步可以刻画为加一个向量，第二步则向原点连线并取 。

其中第二步需要找到移动后的凸壳上与原点相连斜率最大的点，然后将前面的线段去掉，并将该点和原点相连。

容易使用双端队列维护凸壳，队列中装的是向量，从左到右描述相邻两个顶点的差值。

• 将凸壳 的部分去掉。

• 将当前向量 放到队头。

• 若队头的向量的斜率小于下一个向量，则将两者相加。这对应下面的过程。

  

  不难发现，这可以实现我们想要的效果。

（需要维护各项量的和，以便回答询问）

复杂度 。