Wine Factory (Easy Version)

题意翻译

### 题目描述 这是本题的 Easy 版本,与 Hard 不同在于 $c$ 的限制不同。 有 $n$ 个酒桶,第 $i$ 个酒桶里有 $a_i$ 升水,前面站着一个法力值为 $b_i$ 的人。同时,酒桶 $i$ 与 $i+1$ 之间有容量为 $c_i$ 的管子。 现在开始把水酿成酒。从第 $1$ 个酒桶开始,按 $1,2, \dots,n$ 的顺序依次进行。当操作到水桶 $i$ 时,水桶 $i$ 前的人会依次进行以下操作: - 将当前酒桶的水取出最多 $b_i$ 升酿成酒。 - 若当前不是水桶 $n$,则当前水桶里的水全部流向水桶 $i+1$,且最多只能流 $c_i$ 升。 定义 $W(a,b,c)$ 为,当前的数组 $a,b,c$ 下,产生酒升数的值。 现在给出 $q$ 次操作,每次操作给出 $p,x,y,z$ 四个正整数,表示将 $a_p$ 变为 $x$,$b_p$ 变为 $y$,$c_p$ 变为 $z$。每次操作会对后续持续产生影响。对于每次操作,请输出当前的 $W(a,b,c)$ 的值。特别的,当 $p=n$ 时,对 $c_p$ 的修改**没有意义**。 ### 数据范围 $1 \le p \le n \le 5 \times 10^5$,$0 \le a_i,b_i,x,y \le 10^9$,$c_i,z = 10^{18}$,$1 \le q \le 5 \times 10^5$。

题目描述

This is the easy version of the problem. The only difference between the two versions is the constraint on $ c_i $ and $ z $ . You can make hacks only if both versions of the problem are solved. There are three arrays $ a $ , $ b $ and $ c $ . $ a $ and $ b $ have length $ n $ and $ c $ has length $ n-1 $ . Let $ W(a,b,c) $ denote the liters of wine created from the following process. Create $ n $ water towers. The $ i $ -th water tower initially has $ a_i $ liters of water and has a wizard with power $ b_i $ in front of it. Furthermore, for each $ 1 \le i \le n - 1 $ , there is a valve connecting water tower $ i $ to $ i + 1 $ with capacity $ c_i $ . For each $ i $ from $ 1 $ to $ n $ in this order, the following happens: 1. The wizard in front of water tower $ i $ removes at most $ b_i $ liters of water from the tower and turns the removed water into wine. 2. If $ i \neq n $ , at most $ c_i $ liters of the remaining water left in water tower $ i $ flows through the valve into water tower $ i + 1 $ . There are $ q $ updates. In each update, you will be given integers $ p $ , $ x $ , $ y $ and $ z $ and you will update $ a_p := x $ , $ b_p := y $ and $ c_p := z $ . After each update, find the value of $ W(a,b,c) $ . Note that previous updates to arrays $ a $ , $ b $ and $ c $ persist throughout future updates.

输入输出格式

输入格式


The first line contains two integers $ n $ and $ q $ ( $ 2 \le n \le 5\cdot 10^5 $ , $ 1 \le q \le 5\cdot 10^5 $ ) — the number of water towers and the number of updates. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the number of liters of water in water tower $ i $ . The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 0 \le b_i \le 10^9 $ ) — the power of the wizard in front of water tower $ i $ . The fourth line contains $ n - 1 $ integers $ c_1, c_2, \ldots, c_{n - 1} $ ( $ c_i \color{red}{=} 10^{18} $ ) — the capacity of the pipe connecting water tower $ i $ to $ i + 1 $ . Each of the next $ q $ lines contains four integers $ p $ , $ x $ , $ y $ and $ z $ ( $ 1 \le p \le n $ , $ 0 \le x, y \le 10^9 $ , $ z \color{red}{=} 10^{18} $ ) — the updates done to arrays $ a $ , $ b $ and $ c $ . Note that $ c_n $ does not exist, so the value of $ z $ does not matter when $ p = n $ .

输出格式


Print $ q $ lines, each line containing a single integer representing $ W(a, b, c) $ after each update.

输入输出样例

输入样例 #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

说明

The first update does not make any modifications to the arrays. - When $ i = 1 $ , there are $ 3 $ liters of water in tower 1 and $ 1 $ liter of water is turned into wine. The remaining $ 2 $ liters of water flow into tower 2. - When $ i = 2 $ , there are $ 5 $ liters of water in tower 2 and $ 4 $ liters of water is turned into wine. The remaining $ 1 $ liter of water flows into tower 3. - When $ i = 3 $ , there are $ 4 $ liters of water in tower 3 and $ 2 $ liters of water is turned into wine. The remaining $ 2 $ liters of water flows into tower 4. - When $ i = 4 $ , there are $ 5 $ liters of water in tower 4. All $ 5 $ liters of water are turned into wine. Hence, $ W(a,b,c)=1 + 4 + 2 + 5 = 12 $ after the first update. The second update modifies the arrays to $ a = [3, 5, 3, 3] $ , $ b = [1, 1, 2, 8] $ , and $ c = [10^{18}, 10^{18}, 10^{18}] $ . - When $ i = 1 $ , there are $ 3 $ liters of water in tower 1 and $ 1 $ liter of water is turned into wine. The remaining $ 2 $ liters of water flow into tower 2. - When $ i = 2 $ , there are $ 7 $ liters of water in tower 2 and $ 1 $ liter of water is turned into wine. The remaining $ 6 $ liters of water flow into tower 3. - When $ i = 3 $ , there are $ 9 $ liters of water in tower 3 and $ 2 $ liters of water is turned into wine. The remaining $ 7 $ liters of water flow into tower 4. - When $ i = 4 $ , there are $ 10 $ liters of water in tower 4. Only $ 8 $ liters of water is turned into wine. Hence, $ W(a,b,c)=1 + 1 + 2 + 8 = 12 $ after the second update. The third update modifies the arrays to $ a = [3, 5, 0, 3] $ , $ b = [1, 1, 0, 8] $ , and $ c = [10^{18}, 10^{18}, 10^{18}] $ . - When $ i = 1 $ , there are $ 3 $ liters of water in tower 1 and $ 1 $ liter of water is turned into wine. The remaining $ 2 $ liters of water flow into tower 2. - When $ i = 2 $ , there are $ 7 $ liters of water in tower 2 and $ 1 $ liter of water is turned into wine. The remaining $ 6 $ liters of water flow into tower 3. - When $ i = 3 $ , there are $ 6 $ liters of water in tower 3 and $ 0 $ liters of water is turned into wine. The remaining $ 6 $ liters of water flow into tower 4. - When $ i = 4 $ , there are $ 9 $ liters of water in tower 4. Only $ 8 $ liters of water is turned into wine. Hence, $ W(a,b,c)=1 + 1 + 0 + 8 = 10 $ after the third update.