← 返回题目列表

AtCoder · dwango2017qual_e

E. 奇偶糖果分享

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

配点 : 1200 点

問題文

N + 2 盘子排成一排。从左边开始按顺序放置这些盘子。 将其编号为 0, 皿 1, ..., 皿 N+1 。菜 1 卡拉菜 N 最多 N 每个盘子上都有一些糖果,并且盘子 0 和板 N+1 上面没有糖果。

Niwango-kun和niconico TV-chan正试图通过以下方式来分配这些糖果。

  1. 皿 1 卡拉菜 N 之前的每个盘子,将该盘子上的所有糖果移动到左侧或右侧的盘子上。这个移动是在确定每个板的左右方向后同时进行的。
  2. 移除该行中所有没有糖果的盘子。
  3. 在剩余的盘子中,放置从左边算起的奇数(1, 3, 5, ...th) 在盘子里,二王后君拿起了偶数编号的糖果 (2, 4, 6, ...th) Niconico TV-chan收到盘子里的糖果。

二王后君有步骤来获得尽可能多的糖果。 我想确定糖果在 1 中移动的方向。请为二王后君制作一个如下所示的程序。

最初、皿 i (1 ≦ i ≦ N) 是 假设上面有 A_i 块糖果。之后,更改糖果数量的查询是 您将获得 Q 件,请按顺序处理。 第j (1 ≦ j ≦ Q) 个查询是 2 整数 给出 K_j 和 X_j 由一块板组成 K_j 上的糖果数量 这意味着更改为 X_j 。

各 j (1 ≦ j ≦ Q),而j 当二王后君和Nico Nico TV-chan在处理完第一个查询后使用上述方法划分糖果时,请输出二王后君将收到的最大糖果数量。 如果正确答案是满足

制約

  • 1≦N≦5 \times 10^4
  • 1≦A_i≦10^4
  • 1≦Q≦5 \times 10^4
  • 1≦K_j≦N
  • 1≦X_j≦10^4

部分点

  • Q=1 的数据集,700 点。

入力

输入将以以下形式从标准输入给出。

N
A_1 A_2 ... A_N
Q
K_1 X_1
:
K_Q X_Q

出力

Q 行。j (1 ≦ j ≦ Q) 行包含j 当二王后君和Nico Nico TV-chan在处理到第一个查询后分割糖果时,输出二王后君可以接收的最大糖果数量。


入力例 1

6
3 1 4 1 5 9
1
1 3

出力例 1

21

这是满足部分点条件的情况。一开始,盘子里的糖果数量是从左边的盘子开始计算的。 0, 3, 1, 4, 1, 5, 9, 0 。

这里,盘子 对于 1 到 6 ,如果将盘子上的糖果向右,向右,向左,向右,向左,向右移动,糖果的数量将为 0, 0, 7, 1, 5, 1, 0, 9 。

接下来,移除所有没有糖果的盘子。 7, 1, 5, 1, 9 ,左起奇数盘上的糖果总数为 21 。在这种情况下,这就是二王后君收到最多糖果的模式。


入力例 2

5
1 2 3 4 5
1
1 1

出力例 2

11

这是满足部分点条件的情况。


入力例 3

8
2 5 2 5 2 5 2 5
5
1 7
6 1
3 6
8 3
2 9

出力例 3

27
24
24
22
26

该输入/输出示例不满足部分点条件。