题目内容

塔子哥是一个年轻的魔法学徒，他一直在努力学习各种魔法技能。他听说倒水魔法是一种非常强大的魔法，但也是一种非常难掌握的魔法。他早早地来到了魔法训练室，希望能够掌握这种魔法。

魔法训练室里有 $n$ 个神奇的杯子，有着不同的大，假设第 $i$ 个杯子已满，向其倒水，多余的水会正正好好流向第 $i+1$ 个杯子(如果 $i=n$ 时没有下一个杯子，不会有杯子接住此时多余的水而溢出到魔法训练室的水池）。

这些杯子有着初始固定的水量，每次练习后杯子里的水都会还原到最初状态。每次练习时，魔法黑板会告诉塔子哥需要将哪一人杯子倒满水。因为每个杯子的材质和形状有所不同所以对其释放倒水魔法需要消耗的魔法值不同。塔子哥想尽可能多练习，所以需要最小化每次消耗的魔法值的总量。

思路:贪心+前缀和

对于第 $q_i$ 次询问，目标是将第 $j$ 个杯子装满，那么选择从第 $k (k\leq j)$ 个杯子开始倒水，那么 $[k, j]$ 这些杯子被装满的水均来自第 $k$ 个杯子溢出的。

选择从第 $k (k\leq j)$ 个杯子开始倒水，则需要使得$[k+1,j]$ 这些杯子都倒满，魔力值为 $z_k\times \sum\limits_{i=k}^j (x_i-y_i)$。答案即

此外,代码中使用了一个 trick，就是对于每个查询，从 $j$ 到 $1$ 来枚举从每个杯子开始倒水(而不是从$1$到$j$)，这样我们就可以维护这其中需要添加的水量。因为如果是从 $1$ 到 $j$ 来枚举，则对于每次的倒水量都需要 $O(n)$ 去查询，导致总复杂度是$O(n^3)$ ， 当然也可以直接使用前缀和来维护。