P16541 [EGOI 2026] 饼干 / Biscuits

Aurora 和 Bianca 特别喜欢意大利杏仁饼干，今天，她们的爷爷烤了一大堆饼干（形成一个栈）。为了分这些饼干，她们发明了以下游戏。只要栈里还有饼干，她们就重复以下步骤： + Aurora 选一个整数 $X \geq 0$。 + 接下来，Bianca 选一个整数 $Y \geq 0$，满足： - 剩下的饼干至少有 $Y$ 个，并且 - $Y \neq X$。 + 然后 Aurora 吃掉最顶上的 $Y$ 个饼干（如果 $Y=0$ 就不吃）。 + 最后，如果还有剩下的饼干，Bianca 会吃掉最顶上的那一块。 当然，两个女生都想吃得越多越好。栈里的每块饼干都有一个重量 $1 \leq W_i \leq 50$。当所有饼干被吃完后，每个人的**幸福度**等于她在游戏中吃掉的所有饼干的重量总和。两个女生都知道如何最优地玩这个游戏——每个人总是会做出能让自己的最终幸福度最大化的选择。 因为这个游戏太好玩了，她们现在每天都要玩！在接下来的 $Q$ 天里，她们的爷爷每天都会烤一堆同样数量的饼干。为了让游戏更有趣，爷爷每天会改变其中一块饼干的重量，而其他饼干的重量保持不变。 对于初始的饼干堆，以及在每天进行改变之后，你需要计算出每天游戏结束时 **Bianca 的幸福度**。

输入的第一行包含两个整数 $N$ 和 $Q$，分别是饼干的数量和变更的次数。饼干从上到下编号为 $0$ 到 $N-1$。 第二行包含 $N$ 个整数 $W_0, W_1, \dots, W_{N-1}$，即饼干的初始重量。 接下来的 $Q$ 行中，第 $i$ 行包含两个整数 $P_i$ 和 $Z_i$，描述第 $i$ 次变更：爷爷将第 $P_i$ 块饼干的重量改为 $Z_i$。换句话说，$W_{P_i}$ 的值变成了 $Z_i$。

输出 $Q + 1$ 个整数，即每天游戏结束后 Bianca 的幸福度。

### 样例解释 **第一个样例。** 第一天，饼干的重量分别是 $10$ 和 $15$。 - Aurora 选择 $X=1$ 是最优的。然后，Bianca 选择 $Y = 0$ 并吃掉最顶上的饼干。 - 在第二回合，Aurora 选择 $X = 0$。Bianca 唯一的选择是 $Y=1$。然后，Aurora 吃掉重量为 $15$ 的饼干，游戏结束。 第二天，第 $1$ 号饼干的重量变为 $1$，此时饼干的重量为 $[10, 1]$。 - Aurora 选择 $X=0$ 是最优的。然后，Bianca 选择 $Y = 1$。Aurora 吃掉最顶上的饼干，Bianca 吃掉剩下的一块。 游戏结束后，Bianca 的幸福度为 $1$。 **第二个样例。** 初始时，从上到下的饼干重量为 $[1,1,1,1,2]$。 - Aurora 选择 $X = 0$ 是最优的。Bianca 选择 $Y = 1$。Aurora 吃掉第一块，Bianca 吃掉第二块。 - 下一回合，Aurora 选择 $X = 0$。Bianca 选择 $Y = 2$。Aurora 吃掉接下来的两块，Bianca 吃掉最后一块。游戏结束时，Bianca 的总幸福度为 $3$。 第一次变更后，重量变为 $[1,1,20,1,2]$。 - 现在 Aurora 选择 $X=2$ 是最优的。（如果她选其他值，Bianca 会选择 $Y = 2$，那么 Aurora 就吃不到中间那块大饼干了。）响应 Aurora 的选择，Bianca 选择 $Y = 0$ 并吃掉第一块饼干。剩下的饼干重量为 $[1,20,1,2]$。 - 第二回合，Aurora 选择 $X = 1$，Bianca 选择 $Y = 0$。Bianca 再次吃掉最顶上的饼干。之后，剩下的饼干重量为 $[20,1,2]$。 - 第三回合，Aurora 选择 $X=0$。Bianca 选择 $Y = 2$。之后，Aurora 吃掉重量为 $20$ 和 $1$ 的饼干，最后 Bianca 吃掉最后一块重量为 $2$ 的饼干。Bianca 吃掉的饼干总重量为 $1+1+2 = 4$。 第二次变更后，重量变为 $[1,1,20,30,2]$。 如果两个女生都以最优策略进行游戏，Bianca 会吃掉除重量为 $30$ 的那块以外的所有饼干。 ### 约束条件 - $2 \leq N \leq 100\ 000$。 - $0 \leq Q \leq 100\ 000$。 - $1 \leq W_i \leq 50$（是的，意大利杏仁饼干很轻！）。 - $0 \leq P_i \leq N-1$ 且 $1 \leq Z_i \leq 50$。 ### 评分方式 你的程序将在分成若干子任务的测试数据上进行测试。 要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。 - **子任务 0** [$0$ 分]: 样例。 - **子任务 1** [$8$ 分]: $Q = 0$ 且 $W_i = 1$。 - **子任务 2** [$9$ 分]: $N \le 3, Q \le 5$。 - **子任务 3** [$11$ 分]: 在任何时候，饼干重量 $W_i$ 都是非递增的；换句话说，$W_0 \ge W_1 \ge ... \ge W_{N-1}$。 - **子任务 4** [$13$ 分]: $N \le 100, Q \le 50$。 - **子任务 5** [$18$ 分]: $N \le 20\,000, Q \le 50$。 - **子任务 6** [$12$ 分]: $N \le 20\,000, Q \le 5000$。 - **子任务 7** [$29$ 分]: 没有额外的约束条件。