#P9790. [ROIR 2020 Day 2] 海报

[ROIR 2020 Day 2] 海报

题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

接下来 qq 行每行两个整数 pi, vip_i,~v_i,描述一次更换。

输出格式

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

6
1 2 3 4 5 6
2
6 0
2 5
17
13
15

提示

【样例 1 解释】

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

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

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

【数据范围】

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

各子任务如下:

子任务编号 分值 限制
11 1111
22 1212 4n10, 0q104 \le n \le 10,~0\le q\le 10
33 1313 4n1000, 0q10004 \le n \le 1000,~0\le q\le 1000
44 1717 4n40000, q=04 \le n \le 40000,~q=0
55 4747 4n40000,0q400004 \le n \le 40000, 0\le q\le 40000