CF1919F2.Wine Factory (Hard Version)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

This is the hard version of the problem. The only difference between the two versions is the constraint on cic_i and zz . You can make hacks only if both versions of the problem are solved.

There are three arrays aa , bb and cc . aa and bb have length nn and cc has length n1n-1 . Let W(a,b,c)W(a,b,c) denote the liters of wine created from the following process.

Create nn water towers. The ii -th water tower initially has aia_i liters of water and has a wizard with power bib_i in front of it. Furthermore, for each 1in11 \le i \le n - 1 , there is a valve connecting water tower ii to i+1i + 1 with capacity cic_i .

For each ii from 11 to nn in this order, the following happens:

  1. The wizard in front of water tower ii removes at most bib_i liters of water from the tower and turns the removed water into wine.
  2. If ini \neq n , at most cic_i liters of the remaining water left in water tower ii flows through the valve into water tower i+1i + 1 .

There are qq updates. In each update, you will be given integers pp , xx , yy and zz and you will update ap:=xa_p := x , bp:=yb_p := y and cp:=zc_p := z . After each update, find the value of W(a,b,c)W(a,b,c) . Note that previous updates to arrays aa , bb and cc persist throughout future updates.

输入格式

The first line contains two integers nn and qq ( 2n51052 \le n \le 5\cdot 10^5 , 1q51051 \le q \le 5\cdot 10^5 ) — the number of water towers and the number of updates.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n ( 0ai1090 \le a_i \le 10^9 ) — the number of liters of water in water tower ii .

The third line contains nn integers b1,b2,,bnb_1, b_2, \ldots, b_n ( 0bi1090 \le b_i \le 10^9 ) — the power of the wizard in front of water tower ii .

The fourth line contains n1n - 1 integers c1,c2,,cn1c_1, c_2, \ldots, c_{n - 1} ( 0ci10180 \le c_i \color{red}{\le} 10^{18} ) — the capacity of the pipe connecting water tower ii to i+1i + 1 .

Each of the next qq lines contains four integers pp , xx , yy and zz ( 1pn1 \le p \le n , 0x,y1090 \le x, y \le 10^9 , 0z10180 \le z \color{red}{\le} 10^{18} ) — the updates done to arrays aa , bb and cc .

Note that cnc_n does not exist, so the value of zz does not matter when p=np = n .

输出格式

Print qq lines, each line containing a single integer representing W(a,b,c)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

    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 3

    输出#2

    31
    25
    29
    21
    23

说明/提示

The first update does not make any modifications to the arrays.

  • When i=1i = 1 , there are 33 liters of water in tower 1 and 11 liter of water is turned into wine. The remaining 22 liters of water flow into tower 2.
  • When i=2i = 2 , there are 55 liters of water in tower 2 and 44 liters of water is turned into wine. The remaining 11 liter of water flows into tower 3.
  • When i=3i = 3 , there are 44 liters of water in tower 3 and 22 liters of water is turned into wine. Even though there are 22 liters of water remaining, only 11 liter of water can flow into tower 4.
  • When i=4i = 4 , there are 44 liters of water in tower 4. All 44 liters of water are turned into wine.

Hence, W(a,b,c)=1+4+2+4=11W(a,b,c)=1 + 4 + 2 + 4 = 11 after the first update.

The second update modifies the arrays to a=[3,5,3,3]a = [3, 5, 3, 3] , b=[1,1,2,8]b = [1, 1, 2, 8] , and c=[5,1,1]c = [5, 1, 1] .

  • When i=1i = 1 , there are 33 liters of water in tower 1 and 11 liter of water is turned into wine. The remaining 22 liters of water flow into tower 2.
  • When i=2i = 2 , there are 77 liters of water in tower 2 and 11 liter of water is turned into wine. Even though there are 66 liters of water remaining, only 11 liter of water can flow to tower 3.
  • When i=3i = 3 , there are 44 liters of water in tower 3 and 22 liters of water is turned into wine. Even though there are 22 liters of water remaining, only 11 liter of water can flow into tower 4.
  • When i=4i = 4 , there are 44 liters of water in tower 4. All 44 liters of water are turned into wine.

Hence, W(a,b,c)=1+1+2+4=8W(a,b,c)=1 + 1 + 2 + 4 = 8 after the second update.

The third update modifies the arrays to a=[3,5,0,3]a = [3, 5, 0, 3] , b=[1,1,0,8]b = [1, 1, 0, 8] , and c=[5,1,0]c = [5, 1, 0] .

  • When i=1i = 1 , there are 33 liters of water in tower 1 and 11 liter of water is turned into wine. The remaining 22 liters of water flow into tower 2.
  • When i=2i = 2 , there are 77 liters of water in tower 2 and 11 liter of water is turned into wine. Even though there are 66 liters of water remaining, only 11 liter of water can flow to tower 3.
  • When i=3i = 3 , there is 11 liter of water in tower 3 and 00 liters of water is turned into wine. Even though there is 11 liter of water remaining, no water can flow to tower 4.
  • When i=4i = 4 , there are 33 liters of water in tower 4. All 33 liters of water are turned into wine.

Hence, W(a,b,c)=1+1+0+3=5W(a,b,c)=1 + 1 + 0 + 3 = 5 after the third update.

首页