AT_dwango2017qual_e 偶奇飴分け

有 $N + 2$ 个盘子排成一列。这些盘子从左到右依次编号为盘子 $0$, 盘子 $1$, ..., 盘子 $N+1$。盘子 $1$ 到盘子 $N$ 上分别有一定数量的糖果，而盘子 $0$ 和盘子 $N+1$ 上没有糖果。 尼万戈君和尼可尼可电视酱决定通过以下步骤来分配这些糖果： 1. 对于每个盘子（从盘子 $1$ 到盘子 $N$），将其上的所有糖果移到左边或右边的相邻盘子中。这个移动是在决定每个盘子的移动方向后同时进行的。 2. 删除所有没有糖果的盘子。 3. 在剩下的盘子中，尼万戈君将获得奇数顺序（即第 $1$, $3$, $5$, ... 个）的盘子上的糖果，而尼可尼可电视酱将获得偶数顺序（即第 $2$, $4$, $6$, ... 个）的盘子上的糖果。 尼万戈君想选择糖果的最佳移动方向，以便获取最多的糖果。请编写一个程序帮助尼万戈君实现这一目标。 初始时，盘子 $i$ ($1 \leq i \leq N$) 上有 $A_i$ 个糖果。接着，将有 $Q$ 个查询操作，每个操作更新一个盘子的糖果数量。第 $j$ 个查询是两个整数 $K_j$ 和 $X_j$，表示将盘子 $K_j$ 上的糖果数量改为 $X_j$ 个。 对于每个 $j$ (1 ≤ j ≤ Q)，输出在处理了前 $j$ 个查询后的状态下，尼万戈君能够获得的糖果数量的最大值。

输入以以下格式给出： > $N$ $A_1$ $A_2$ ... $A_N$ $Q$ $K_1$ $X_1$ ... $K_Q$ $X_Q$

输出共 $Q$ 行。第 $j$ ($1\leq j\leq Q$) 行表示在处理了前 $j$ 个查询后的状态下，尼万戈君能够获得的最大糖果数量。

- $1 \leq N \leq 5 \times 10^4$ - $1 \leq A_i \leq 10^4$ - $1 \leq Q \leq 5 \times 10^4$ - $1 \leq K_j \leq N$ - $1 \leq X_j \leq 10^4$ ### 部分分数 如果您正确地解决了只有 $Q = 1$ 的数据集，可以获得 700 分。 ### 样例解释 1 这是一个满足部分分数条件的例子。初始时，盘子中的糖果数量从左到右依次为 $0$, $3$, $1$, $4$, $1$, $5$, $9$, $0$。若将盘子 $1$ 到 $6$ 上的糖果分别按右、右、左、右、左、右的方向移动，糖果的数量将变成 $0$, $0$, $7$, $1$, $5$, $1$, $0$, $9$。移除没有糖果的盘子后，留下的盘子中，糖果总数为 $21$（奇数顺序盘子上糖果数），这是尼万戈君能获得的最多糖果的情况。 **本翻译由 AI 自动生成**