#3264. 「ROIR 2020 Day 2」海报

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: ksyx

题目描述

译自 ROIR 2020 Day2 T4. Плакаты

你的朋友们为了会见 IOI 回来的国家队选手准备了很多漂亮的海报,现在就还差要考虑些细节了。

为了欢迎这些选手,你的 n 个朋友会拿着海报站成一个圈。为了方便描述,我们把他们编号为朋友 1\ldots n ,其中对于 i\in [1,n-1] ,朋友 i 和朋友 i+1 站在一起,且朋友 n 和朋友 1 站在一起。

每张海报都有一个美观度,其中朋友 i 拿着的海报的美观度为 a_i 。当开始庆祝时,一些朋友会举起他们的海报。为了美观,不能有 4 个或以上排在一起的朋友同时举起他们的海报。

为了能够丰富节目效果,你的朋友们还打算在庆祝过程中更换 q 次海报。每次更换后,海报 p_i 的美观度将变为 q_i 。你的朋友想知道每次更换后在符合上述条件下的最大美观度之和。

你的任务是给出初始的美观度,求出初始以及各次更换后的最大美观度之和。

译者注:题面省略了部分难以理解的不必要细节。

输入格式

第一行一个整数 n ,朋友总数。

接下来一行 n 个整数 a_i ,表示初始美观度。

第三行 q 个整数表示海报更换次数。

接下来 q 行每行两个整数 p_i,~v_i ,描述一次更换。

输出格式

输出 q+1 行,表示初始时及各次更换后最大的美观度之和。

样例

样例输入

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

样例输出

17
13
15

样例解释

初始状态下最佳方案为让朋友 2,~4,~5,~6 举起海报,此时美观度之和为 17

第一次改变后朋友 6 的海报美观度变为 0 ,在此情况下最佳方案为让朋友 1,~3,~4,~5 举起海报,美观度之和为 13

第二次改变后朋友 2 的海报美观度变为 5 ,在此情况下最佳方案为让朋友 1,~2,~4,~5 举起海报,美观度之和为 15

数据范围与提示

对于 100\% 的数据,有 4\le n\le 40000, ~0\le a_i,~v_i\le 10^9, ~1\le p_i\le n, ~0\le q\le 40000

子任务绑定暂不支持(2020/2/28),请忽略。

各子任务如下:

子任务编号 子任务绑定 分值 限制
1 11 4 \le n \le 10,~q=0
2 1 12 4 \le n \le 10,~0\le q\le 10
3 1,~2 13 4 \le n \le 1000,~0\le q\le 1000
4 1 17 4 \le n \le 40000,~q=0
5 1,~2,~3,~4 47 4 \le n \le 40000, 0\le q\le 40000