CF1919F1 Wine Factory (Easy Version)

这是该问题的简单版本。两个版本的唯一区别在于 $c_i$ 和 $z$ 的约束条件。只有当你同时解决了两个版本的问题时，才能进行 hack。 有三个数组 $a$、$b$ 和 $c$。$a$ 和 $b$ 的长度为 $n$，$c$ 的长度为 $n-1$。令 $W(a,b,c)$ 表示通过以下过程产生的葡萄酒的升数。 建立 $n$ 个水塔。第 $i$ 个水塔初始有 $a_i$ 升水，且前面站着一个法力为 $b_i$ 的巫师。此外，对于每个 $1 \le i \le n-1$，有一个容量为 $c_i$ 的阀门连接水塔 $i$ 和 $i+1$。 对于每个 $i$ 从 $1$ 到 $n$，依次进行以下操作： 1. 水塔 $i$ 前的巫师最多从水塔中取出 $b_i$ 升水，并将取出的水变成葡萄酒。 2. 如果 $i \neq n$，则水塔 $i$ 剩余的水中，最多有 $c_i$ 升水通过阀门流入水塔 $i+1$。 有 $q$ 次更新。每次更新，你会得到整数 $p$、$x$、$y$ 和 $z$，并将 $a_p := x$，$b_p := y$，$c_p := z$。每次更新后，求 $W(a,b,c)$ 的值。注意，之前对数组 $a$、$b$ 和 $c$ 的修改会在后续更新中持续生效。 注意，当 $p = n$ 时，$c_n$ 不存在，因此 $z$ 的值无关紧要。

第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 5 \cdot 10^5$，$1 \le q \le 5 \cdot 10^5$）——水塔的数量和更新次数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）——第 $i$ 个水塔中的水量。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \le 10^9$）——第 $i$ 个水塔前巫师的法力。 第四行包含 $n-1$ 个整数 $c_1, c_2, \ldots, c_{n-1}$（$c_i \color{red}{=} 10^{18}$）——连接水塔 $i$ 和 $i+1$ 的管道容量。 接下来的 $q$ 行，每行包含四个整数 $p$、$x$、$y$ 和 $z$（$1 \le p \le n$，$0 \le x, y \le 10^9$，$z \color{red}{=} 10^{18}$）——对数组 $a$、$b$ 和 $c$ 的一次更新。 注意，$c_n$ 不存在，因此当 $p = n$ 时，$z$ 的值无关紧要。

输出 $q$ 行，每行一个整数，表示每次更新后 $W(a, b, c)$ 的值。

第一次更新不会对数组做任何修改。 - 当 $i = 1$ 时，水塔 1 有 3 升水，1 升水被变成葡萄酒，剩下的 2 升水流入水塔 2。 - 当 $i = 2$ 时，水塔 2 有 5 升水，4 升水被变成葡萄酒，剩下的 1 升水流入水塔 3。 - 当 $i = 3$ 时，水塔 3 有 4 升水，2 升水被变成葡萄酒，剩下的 2 升水流入水塔 4。 - 当 $i = 4$ 时，水塔 4 有 5 升水，全部 5 升水被变成葡萄酒。 因此，第一次更新后 $W(a,b,c)=1+4+2+5=12$。 第二次更新后，数组变为 $a=[3,5,3,3]$，$b=[1,1,2,8]$，$c=[10^{18},10^{18},10^{18}]$。 - 当 $i = 1$ 时，水塔 1 有 3 升水，1 升水被变成葡萄酒，剩下的 2 升水流入水塔 2。 - 当 $i = 2$ 时，水塔 2 有 7 升水，1 升水被变成葡萄酒，剩下的 6 升水流入水塔 3。 - 当 $i = 3$ 时，水塔 3 有 9 升水，2 升水被变成葡萄酒，剩下的 7 升水流入水塔 4。 - 当 $i = 4$ 时，水塔 4 有 10 升水，只有 8 升水被变成葡萄酒。 因此，第二次更新后 $W(a,b,c)=1+1+2+8=12$。 第三次更新后，数组变为 $a=[3,5,0,3]$，$b=[1,1,0,8]$，$c=[10^{18},10^{18},10^{18}]$。 - 当 $i = 1$ 时，水塔 1 有 3 升水，1 升水被变成葡萄酒，剩下的 2 升水流入水塔 2。 - 当 $i = 2$ 时，水塔 2 有 7 升水，1 升水被变成葡萄酒，剩下的 6 升水流入水塔 3。 - 当 $i = 3$ 时，水塔 3 有 6 升水，0 升水被变成葡萄酒，剩下的 6 升水流入水塔 4。 - 当 $i = 4$ 时，水塔 4 有 9 升水，只有 8 升水被变成葡萄酒。 因此，第三次更新后 $W(a,b,c)=1+1+0+8=10$。 由 ChatGPT 4.1 翻译