CF1919F2 Wine Factory (Hard 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$，水塔 $i$ 与 $i+1$ 之间有一根容量为 $c_i$ 的阀门相连。 对于每个 $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}$（$0 \le c_i \le 10^{18}$）——水塔 $i$ 与 $i+1$ 之间的管道容量。 接下来的 $q$ 行，每行包含四个整数 $p$、$x$、$y$ 和 $z$（$1 \le p \le n$，$0 \le x, y \le 10^9$，$0 \le z \le 10^{18}$）——对数组 $a$、$b$ 和 $c$ 的一次修改。 注意，当 $p = n$ 时，$c_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$ 升，但只有 $1$ 升能流入水塔 4。 - 当 $i=4$ 时，水塔 4 有 $4$ 升水，全部 $4$ 升被转化为葡萄酒。 因此，第一次操作后 $W(a,b,c)=1+4+2+4=11$。 第二次操作后，数组变为 $a=[3,5,3,3]$，$b=[1,1,2,8]$，$c=[5,1,1]$。 - 当 $i=1$ 时，水塔 1 有 $3$ 升水，$1$ 升被转化为葡萄酒，剩余 $2$ 升流入水塔 2。 - 当 $i=2$ 时，水塔 2 有 $7$ 升水，$1$ 升被转化为葡萄酒。虽然剩余 $6$ 升，但只有 $1$ 升能流入水塔 3。 - 当 $i=3$ 时，水塔 3 有 $4$ 升水，$2$ 升被转化为葡萄酒。虽然剩余 $2$ 升，但只有 $1$ 升能流入水塔 4。 - 当 $i=4$ 时，水塔 4 有 $4$ 升水，全部 $4$ 升被转化为葡萄酒。 因此，第二次操作后 $W(a,b,c)=1+1+2+4=8$。 第三次操作后，数组变为 $a=[3,5,0,3]$，$b=[1,1,0,8]$，$c=[5,1,0]$。 - 当 $i=1$ 时，水塔 1 有 $3$ 升水，$1$ 升被转化为葡萄酒，剩余 $2$ 升流入水塔 2。 - 当 $i=2$ 时，水塔 2 有 $7$ 升水，$1$ 升被转化为葡萄酒。虽然剩余 $6$ 升，但只有 $1$ 升能流入水塔 3。 - 当 $i=3$ 时，水塔 3 有 $1$ 升水，$0$ 升被转化为葡萄酒。虽然剩余 $1$ 升，但无法流入水塔 4。 - 当 $i=4$ 时，水塔 4 有 $3$ 升水，全部 $3$ 升被转化为葡萄酒。 因此，第三次操作后 $W(a,b,c)=1+1+0+3=5$。 由 ChatGPT 4.1 翻译