A16386 · Wine Factory (Hard Version)

题目描述

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: 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}$ ( $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$ .

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
5 2 1
4 3 8 1000000000
2 5 1 1
3 0 0 0

输出 #1

11
8
5

输入 #2

输出 #2