Hello 2024 |
---|
Закончено |
Это сложная версия задачи. Единственное различие между двумя версиями заключается в ограничениях на $$$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$$$.
Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ в этом порядке происходит следующее:
Дано $$$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}$$$ ($$$0 \le c_i \color{red}{\le} 10^{18}$$$) — пропускная способность трубы, соединяющей водонапорную башню $$$i$$$ с $$$i + 1$$$.
Каждая из следующих $$$q$$$ строк содержит четыре целых числа $$$p$$$, $$$x$$$, $$$y$$$ и $$$z$$$ ($$$1 \le p \le n$$$, $$$0 \le x, y \le 10^9$$$, $$$0 \le z \color{red}{\le} 10^{18}$$$) — обновления массивов $$$a$$$, $$$b$$$ и $$$c$$$.
Заметим, что $$$c_n$$$ не существует, поэтому величина $$$z$$$ не имеет значения при $$$p = n$$$.
Выведите $$$q$$$ строк, каждая из которых содержит одно целое число, равняющееся $$$W(a, b, c)$$$ после каждого обновления.
4 33 3 3 31 4 2 85 2 14 3 8 10000000002 5 1 13 0 0 0
11 8 5
5 510 3 8 9 23 4 10 8 16 5 9 25 4 9 11 1 1 12 7 4 84 1 1 11 8 3 3
31 25 29 21 23
Первое обновление не вносит никаких изменений в массивы.
Следовательно, $$$W(a,b,c)=1 + 4 + 2 + 4 = 11$$$ после первого обновления.
Второе обновление изменяет массивы на $$$a = [3, 5, 3, 3]$$$, $$$b = [1, 1, 2, 8]$$$ и $$$c = [5, 1, 1]$$$.
Следовательно, $$$W(a,b,c)=1 + 1 + 2 + 4 = 8$$$ после второго обновления.
Третье обновление изменяет массивы на $$$a = [3, 5, 0, 3]$$$, $$$b = [1, 1, 0, 8]$$$ и $$$c = [5, 1, 0]$$$.
Следовательно, $$$W(a,b,c)=1 + 1 + 0 + 3 = 5$$$ после третьего обновления.
Название |
---|