配点 : 1200 点
問題文
N + 2 盘子排成一排。从左边开始按顺序放置这些盘子。 将其编号为 0, 皿 1, ..., 皿 N+1 。菜 1 卡拉菜 N 最多 N 每个盘子上都有一些糖果,并且盘子 0 和板 N+1 上面没有糖果。
Niwango-kun和niconico TV-chan正试图通过以下方式来分配这些糖果。
- 皿 1 卡拉菜 N 之前的每个盘子,将该盘子上的所有糖果移动到左侧或右侧的盘子上。这个移动是在确定每个板的左右方向后同时进行的。
- 移除该行中所有没有糖果的盘子。
- 在剩余的盘子中,放置从左边算起的奇数(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
该输入/输出示例不满足部分点条件。