这是问题的简单版本。两个版本之间的唯一区别是对 $$$c_i$$$ 和 $$$z$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
共有三个数组 $$$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$$$。
对于按此顺序从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,会发生以下情况:
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$$$ 的更新在未来的更新中仍然存在。
输入
第一行包含两个整数 $$$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)$$$ 的整数。
示例
输入 #1
4 3 3 3 3 3 1 4 2 8 1000000000000000000 1000000000000000000 1000000000000000000 4 3 8 1000000000000000000 2 5 1 1000000000000000000 3 0 0 1000000000000000000
输出 #1
12 12 10
输入 #2
5 5 10 3 8 9 2 3 4 10 8 1 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 5 4 9 1000000000000000000 1 1 1 1000000000000000000 2 7 4 1000000000000000000 4 1 1 1000000000000000000 1 8 3 1000000000000000000
输出 #2
34 25 29 21 27
注意
第一次更新不会对数组进行任何修改。
- 当$$$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$$$。