← 返回题目列表

AtCoder · dwango2015_finals_4

D. 争夺金币

中文机器翻译题面 查看原题

問題文

Niwango-kun 和 Nikomova-chan 正在玩硬币游戏。

简介 N 硬币 1 排成一排,从左到右 它的编号为 1 它们的编号最大为 N 。奇数硬币正面朝上,偶数硬币背面朝上。硬币 i 的值为 S_i 。

这个游戏是 N-1 游戏由回合组成,奇数回合的玩家是 Niwango-kun,偶数回合的玩家是 Nikomova-chan。i 在回合中,玩家收到硬币。 i 或硬币 您可以翻转其中一个 i+1 。如果你也不想翻转,那你也不必翻转。

N-1 回合结束后,Niwango 得到正面朝上的硬币,Nikomova 得到正面朝上的硬币。此时,你所获得的金币的价值总和就是你的分数。这个时候,Niwango的成绩会是多少呢?然而,2 由于人们非常聪明,每个人都会采取最佳策略来最大化他或她的分数。

另外,在开始游戏之前,Nikomova-chan 可能会在硬币上涂鸦,这可能会降低硬币的价值。 Nikomova-chan 完全 Q 涂鸦两次,i 我第一次乱涂乱画的硬币是一枚硬币 P_i 涂鸦硬币 i 的值为 D_i 它下降了。

Q 对于每个涂鸦,如果 Niwango 在涂鸦后立即开始游戏,则计算他的得分。


入力

输入将以以下格式从标准输入提供。

N
S_1 S_2 ... S_N
Q
P_1 D_1
P_2 D_2
:
P_Q D_Q
  • 1 行代表硬币数量。 1 整数 N (2 ≦ N ≦ 200,000) 。 来自行
  • 2 线代表硬币的初始值。 N 整数由空格分隔。其中 i 第一个整数 S_i (1 ≦ S_i ≦ 10^9) 是一枚硬币 表示 i 的初始值。
  • 3 Nikomova-chan 涂鸦的次数显示在第一行。 1 整数 Q (0 ≦ Q ≦ 200,000) 。 来自行
  • 4 从线 Q 行提供了有关 Nikomova-chan 涂鸦的信息。其中 i 第几行包含,2 整数 P_i (1 ≦ P_i ≦ N), D_i (1 ≦ D_i) 用空格分隔。这是i 第二个涂鸦的硬币 P_i 值得 D_i 表示该值已减少。然而,每枚硬币的价值始终是 保证 1 或更高。

部分点

针对此问题设置了部分分数。

  • Q = 0 的数据集 如果您正确回答 1 , 给出10 点。 如果您正确回答
  • S_i ≦ 25 的数据集 如果您正确回答 2 的回答正确,除上述之外, 80 点。 如果您正确回答
  • 如果所有测试用例都回答正确,除了上述之外 90 点。 如果您正确回答

出力

输出是 第 Q+1 行组成。1 行输出从初始状态开始游戏时Niwango的得分,2 从行 Q+1 至行 i (1 ≦ i ≦ Q) 第几行包含,i 如果 Niwango 在第一个涂鸦后立即开始游戏,则输出 Niwango 的得分。还在输出末尾添加换行符。


入力例1

4
1 2 3 4
1
4 3

出力例1

7
5

在此示例中, 有4 个硬币,其面值从左到右排列。 1,2,3,4 。最初,硬币的顶面是两侧。如果从这个状态开始游戏,

  • 二王后君硬币 翻开 2 → Nikomova-chan获得硬币 翻开 3 →Niwango获得硬币 翻转 4 翻

,而最终状态下硬币的顶面是“正面和背面”,所以 Niwango 的得分是 7 点。

另外,在这个例子中 有 1 查询。通过查询硬币 它下降到 4 值得 1 。如果从这个状态开始游戏,

  • 二王后君硬币 翻开 2 → Nikomova-chan获得硬币 翻开 2 →Niwango获得硬币 翻转 4 翻

,而最终状态下硬币的顶面是“正面和背面”,所以 Niwango 的得分是 5 点。


入力例2

8
3 1 4 1 5 9 2 6
5
3 3
6 6
8 4
1 1
6 2

出力例2

19
16
16
12
11
11