Это сложная версия задачи. Единственное различие между двумя версиями заключается в ограничениях на \(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\) в этом порядке происходит следующее:
- Волшебник, стоящий перед водонапорной башней \(i\), забирает из башни не более \(b_i\) литров воды и превращает забранную воду в вино.
- Если \(i \neq n\), то не более \(c_i\) литров воды, оставшейся в водонапорной башне \(i\), вытекает через клапан в водонапорную башню \(i + 1\).
Дано \(q\) обновлений. В каждом обновлении вам будут даны целые числа \(p\), \(x\), \(y\) и \(z\), означающие следующие изменения: \(a_p := x\), \(b_p := y\) и \(c_p := z\). После каждого обновления найдите значение \(W(a,b,c)\). Обратите внимание, что предыдущие обновления массивов \(a\), \(b\) и \(c\) сохраняются во всех последующих обновлениях.
Выходные данные
Выведите \(q\) строк, каждая из которых содержит одно целое число, равняющееся \(W(a, b, c)\) после каждого обновления.
Примечание
Первое обновление не вносит никаких изменений в массивы.
- Для \(i = 1\), в башне 1 находится \(3\) литра воды, и \(1\) литр воды превращается в вино. Оставшиеся \(2\) литра воды перетекают в башню 2.
- Для \(i = 2\), в башне 2 находится \(5\) литров воды, и \(4\) литра воды превращаются в вино. Оставшийся \(1\) литр воды попадает в башню 3.
- Для \(i = 3\), в башне 3 находится \(4\) литра воды, и \(2\) литра воды превращаются в вино. Несмотря на то, что осталось \(2\) литра воды, в башню 4 может попасть только \(1\) литр воды.
- Для \(i = 4\), в башне 4 находится \(4\) литра воды. Все \(4\) литра воды превращаются в вино.
Следовательно, \(W(a,b,c)=1 + 4 + 2 + 4 = 11\) после первого обновления.
Второе обновление изменяет массивы на \(a = [3, 5, 3, 3]\), \(b = [1, 1, 2, 8]\) и \(c = [5, 1, 1]\).
- Для \(i = 1\), в башне 1 находится \(3\) литра воды, и \(1\) литр воды превращается в вино. Оставшиеся \(2\) литра воды перетекают в башню 2.
- Для \(i = 2\), в башне 2 находится \(7\) литров воды, и \(1\) литр воды превращается в вино. Несмотря на то, что осталось \(6\) литров воды, только \(1\) литр воды может попасть в башню 3.
- Для \(i = 3\), в башне 3 находится \(4\) литра воды, и \(2\) литра воды превращаются в вино. Несмотря на то, что осталось \(2\) литра воды, только \(1\) литр воды может попасть в башню 4.
- Для \(i = 4\), в башне 4 находится \(4\) литра воды. Все \(4\) литра воды превращаются в вино.
Следовательно, \(W(a,b,c)=1 + 1 + 2 + 4 = 8\) после второго обновления.
Третье обновление изменяет массивы на \(a = [3, 5, 0, 3]\), \(b = [1, 1, 0, 8]\) и \(c = [5, 1, 0]\).
- Для \(i = 1\), в башне 1 находится \(3\) литра воды, и \(1\) литр воды превращается в вино. Оставшиеся \(2\) литра воды перетекают в башню 2.
- Для \(i = 2\), в башне 2 находится \(7\) литров воды, и \(1\) литр воды превращается в вино. Несмотря на то, что осталось \(6\) литров воды, только \(1\) литр воды может попасть в башню 3.
- Для \(i = 3\) в башне 3 находится \(1\) литр воды, и \(0\) литров воды превращается в вино. Несмотря на то, что в башне остался \(1\) литр воды, в башню 4 вода не поступает.
- Для \(i = 4\), в башне 4 находится \(3\) литра воды. Все \(3\) литра воды превращаются в вино.
Следовательно, \(W(a,b,c)=1 + 1 + 0 + 3 = 5\) после третьего обновления.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|
31
25
29
21
23
|