311002: CF1919F2. Wine Factory (Hard Version)
Description
This is the hard 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:
- 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.
- 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.
InputThe 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}$ ($0 \le c_i \color{red}{\le} 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$, $0 \le z \color{red}{\le} 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$.
OutputPrint $q$ lines, each line containing a single integer representing $W(a, b, c)$ after each update.
ExamplesInput4 3 3 3 3 3 1 4 2 8 5 2 1 4 3 8 1000000000 2 5 1 1 3 0 0 0Output
11 8 5Input
5 5 10 3 8 9 2 3 4 10 8 1 6 5 9 2 5 4 9 1 1 1 1 1 2 7 4 8 4 1 1 1 1 8 3 3Output
31 25 29 21 23Note
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. Even though there are $2$ liters of water remaining, only $1$ liter of water can flow into tower 4.
- When $i = 4$, there are $4$ liters of water in tower 4. All $4$ liters of water are turned into wine.
Hence, $W(a,b,c)=1 + 4 + 2 + 4 = 11$ after the first update.
The second update modifies the arrays to $a = [3, 5, 3, 3]$, $b = [1, 1, 2, 8]$, and $c = [5, 1, 1]$.
- 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. Even though there are $6$ liters of water remaining, only $1$ liter of water can flow to tower 3.
- When $i = 3$, there are $4$ liters of water in tower 3 and $2$ liters of water is turned into wine. Even though there are $2$ liters of water remaining, only $1$ liter of water can flow into tower 4.
- When $i = 4$, there are $4$ liters of water in tower 4. All $4$ liters of water are turned into wine.
Hence, $W(a,b,c)=1 + 1 + 2 + 4 = 8$ after the second update.
The third update modifies the arrays to $a = [3, 5, 0, 3]$, $b = [1, 1, 0, 8]$, and $c = [5, 1, 0]$.
- 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. Even though there are $6$ liters of water remaining, only $1$ liter of water can flow to tower 3.
- When $i = 3$, there is $1$ liter of water in tower 3 and $0$ liters of water is turned into wine. Even though there is $1$ liter of water remaining, no water can flow to tower 4.
- When $i = 4$, there are $3$ liters of water in tower 4. All $3$ liters of water are turned into wine.
Hence, $W(a,b,c)=1 + 1 + 0 + 3 = 5$ after the third update.
Output
这个问题是“酒厂”问题的困难版本。两个版本之间唯一的区别是对于c_i和z的约束。只有当两个版本的问题都解决时,你才能进行黑客攻击。
有三个数组a、b和c。a和b的长度为n,c的长度为n-1。W(a,b,c)表示从以下过程中产生的葡萄酒升数。
创建n个水塔。第i个水塔最初有a_i升水,前面有一个功率为b_i的巫师。此外,对于每个1≤i≤n-1,有一个容量为c_i的阀门连接水塔i和水塔i+1。
对于从1到n的每个i,按以下顺序发生:
1. 水塔i前的巫师从塔中取出最多b_i升水,将取出的水变成酒。
2. 如果i≠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≤n≤500000,1≤q≤500000)——水塔的数量和更新的数量。
第二行包含n个整数a_1,a_2,…,a_n(0≤a_i≤10^9)——水塔i中的水量升数。
第三行包含n个整数b_1,b_2,…,b_n(0≤b_i≤10^9)——水塔i前巫师的功率。
第四行包含n-1个整数c_1,c_2,…,c_n-1(0≤c_i≤10^18)——连接水塔i和水塔i+1的管道容量。
接下来的q行中的每一行都包含四个整数p、x、y和z(1≤p≤n,0≤x,y≤10^9,0≤z≤10^18)——对数组a、b和c的更新。
注意,c_n不存在,所以当p=n时,z的值无关紧要。
输出描述:
打印q行,每行包含一个表示每次更新后W(a,b,c)的整数值。题目大意: 这个问题是“酒厂”问题的困难版本。两个版本之间唯一的区别是对于c_i和z的约束。只有当两个版本的问题都解决时,你才能进行黑客攻击。 有三个数组a、b和c。a和b的长度为n,c的长度为n-1。W(a,b,c)表示从以下过程中产生的葡萄酒升数。 创建n个水塔。第i个水塔最初有a_i升水,前面有一个功率为b_i的巫师。此外,对于每个1≤i≤n-1,有一个容量为c_i的阀门连接水塔i和水塔i+1。 对于从1到n的每个i,按以下顺序发生: 1. 水塔i前的巫师从塔中取出最多b_i升水,将取出的水变成酒。 2. 如果i≠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≤n≤500000,1≤q≤500000)——水塔的数量和更新的数量。 第二行包含n个整数a_1,a_2,…,a_n(0≤a_i≤10^9)——水塔i中的水量升数。 第三行包含n个整数b_1,b_2,…,b_n(0≤b_i≤10^9)——水塔i前巫师的功率。 第四行包含n-1个整数c_1,c_2,…,c_n-1(0≤c_i≤10^18)——连接水塔i和水塔i+1的管道容量。 接下来的q行中的每一行都包含四个整数p、x、y和z(1≤p≤n,0≤x,y≤10^9,0≤z≤10^18)——对数组a、b和c的更新。 注意,c_n不存在,所以当p=n时,z的值无关紧要。 输出描述: 打印q行,每行包含一个表示每次更新后W(a,b,c)的整数值。