Задача 8. Плакаты ≡

Условие

Друзья готовятся встретить национальную команду, возвращающуюся с международной олимпиады по информатике. Для этого они подготовили множество красочных плакатов. Осталось только продумать детали поздравления.

Для того, чтобы приветствовать команду, n друзей встанут в круг. Пронумеруем их от 1 до n в порядке их расположения по кругу. Таким образом, для всех i от 1 до n − 1 друзья с номерами i и i + 1 стоят рядом, также рядом стоят друзья с номерами n и 1. У каждого из друзей есть плакат. Каждый плакат характеризуется своей красочностью — целым неотрицательным числом. Плакат у друга с номером i имеет красочность a_i.

Когда поздравление начнётся, некоторые из друзей поднимут свои плакаты и будут показывать их команде. Для того, чтобы члены команды не растерялись и смогли рассмотреть все плакаты, не должно быть четырёх или более стоящих подряд друзей с поднятым плакатом.

Друзья планируют изменять плакаты в процессе встречи. Всего будет внесено q изменений в плакаты. После i-го из них плакат друга с номером p_i будет иметь красочность v_i. После каждого из изменений друзья хотят определить, какую максимальную суммарную красочность могут иметь поднятые плакаты, если нельзя нарушать установленное ограничение.

Требуется написать программу, которая по заданной начальной красочности плакатов и последовательности их изменений определяет в начале, а также после каждого изменения, какой максимальной суммарной красочности поднятых плакатов можно добиться, не нарушая условие, что поднято не более трёх плакатов подряд.

Формат входных данных

Первая строка ввода содержит целое число n (4 ≤ n ≤ 40 000) — количество друзей.

Вторая строка содержит n целых чисел a_i (0 ≤ a_i ≤ 10⁹) — исходные значения красочности плакатов у друзей.

Третья строка содержит одно целое число q (0 ≤ q ≤ 40 000) — количество изменений плакатов, которые вносили друзья.

Каждая из следующих q строк содержит два целых числа p_i и v_i (1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹) — номер друга, плакат которого изменился, и новая красочность этого плаката.

Формат выходных данных

Выведите q + 1 число. Перед первым изменением, а также после каждого изменения плакатов выведите одно целое число — максимальное суммарное значение красочности поднятых плакатов, если нельзя поднимать больше трёх плакатов подряд.

Ограничения

4 ≤ n ≤ 40 000

0 ≤ a_i ≤ 10⁹

0 ≤ q ≤ 40 000

1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения

Перед первым изменением плакаты следует поднять друзьям с номерами 2, 4, 5, 6. Суммарная красочность поднятых плакатов будет равняться 17.

После первого изменения плакат друга с номером 6 имеет красочность 0. Теперь плакаты следует поднять друзьям с номерами 1, 3, 4, 5. Суммарная красочность будет равняться 13.

После второго изменения плакат друга с номером 2 имеет красочность 5. Плакаты следует поднять друзьям с номерами 1, 2, 4, 5. Суммарная красочность будет равняться 15.

Примеры тестов

6
1 2 3 4 5 6
2
6 0
2 5

17
13
15

Разбор

В первой подзадаче можно просто перебрать, кто из друзей поднимет плакаты, для каждого варианта проверить, что нет трёх поднятых подряд плакатов, и посчитать суммарную красочность поднятых плакатов. Время работы решения O(2n ⋅ n).

Во второй подзадаче можно реализовать тот же алгоритм, но повторить его q раз, после каждого изменения. Время работы O(2n ⋅ nq).

Третья и четвертая подзадача решаются с помощью динамического программирования. Заметим, что друзья 1, 2, 3 и 4 не могут одновременно поднять плакат. Переберём, кто из них не поднял плакат, и переставим его и друзей, которые идут до него, в конец нумерации. Теперь стоящий последним друг не поднял плакат, поэтому из задачи на окружности мы получили задачу на прямой. Используем для её решения динамическое программирование: обозначим как dp[i][j] максимальную суммарную красочность плакатов, поднятых первыми i друзьями, причём последние j из них подняли плакат (0 ≤ j ≤ 3). Тогда dp[i][0] = max(dp[i − 1][0],dp[i − 1][1],dp[i − 1][2],dp[i − 1][3]), а для j > 0 выполнено dp[i][j] = dp[i − 1][j − 1] + a_i.

В решении третьей подзадачи запустим этот алгоритм q + 1 раз, для начальной позиции и после каждого изменения, получив решение за O(nq). В четвертой подзадаче один запуск этого алгоритма работает за O(n).

Наконец, для полного решения задачи необходимо научиться изменять величину красочность плакатов и пересчитывать значения dp[i][j]. Потребуется чуть более сложная конструкция: построим дерево отрезков на индексах от 1 до n. В узле, соответствующем отрезку от l до r будем хранить матрицу 4×4: best[a][b] равно максимальной суммарной красочности плакатов, поднятых друзьями, с номерами от l до r, в начале a стоящих подряд друзей подняли плакат, а в конце b подряд стоящих друзей. Тогда объединение двух соседних отрезков происходит по алгоритму, аналогичному пересчёту значений динамического программирования в одной из предыдущих задач. Изменяя значение красочности i-го плаката, нам необходимо пересчитать O(logn) значений в узлах на пути к листу, соответствующему отрезку от i до i.

Время работы получившегося решения есть O(n + q logn), напоследок отметим, что, несмотря на небольшие по меркам получившейся асимптотики ограничения, пересчёт значения в узле дерева отрезков получился довольно трудоёмким, поэтому константа, спрятанная в O довольно велика, и для того, чтобы уложиться в ограничение по времени, необходима достаточно аккуратная реализация.