AT_ndpc2026_g 口

给你一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$。 你需要处理 $Q$ 次询问。每次询问，你会得到一个整数 $i$（$1 \leq i \leq N$）和一个非负整数 $v$。将 $A_i$ 更新为 $v$，然后解决以下问题（所有更新都是永久生效的）： > 有 $N$ 个人，分别站在数轴上的位置 $1$ 到 $N$，每个人的嘴巴是张开的。第 $i$ 个人位于位置 $i$。每个人都有一个称为“饥饿度”的参数，第 $i$ 个人的饥饿度为 $A_i$。 > 你拥有无限个糖果。你决定按以下步骤喂糖（每步都只执行一次）： > > - 首先，选择一个整数 $x$，满足 $1 \leq x \leq N$，你站在位置 $x$。 > - 接下来，你可以进行如下操作任意多次（可以为零次）： > - 假设你当前所在位置是 $y$，你可以移动到 $y-1$、$y$ 或 $y+1$。但你不能移动到没有人站的位置。 > - 向你当前所在位置的人嘴里扔一个糖果。 > > 所有操作结束后，令 $B_i$ 表示第 $i$ 个人收到了多少个糖果。请你求出 $\displaystyle \sum_{i=1}^N \vert A_i - B_i \vert$ 的最小可能值。

输入从标准输入读入，格式如下： > $N\ Q\ A_1\ A_2\ \dots\ A_N\ \mathrm{query}_1\ \mathrm{query}_2\ \vdots\ \mathrm{query}_Q$ 每个询问格式为： > $i\ v$

输出共 $Q$ 行。第 $i$ 行输出第 $i$ 次询问的答案。

### 部分得分 本题有部分分。 - 如果你能解决 $Q \leq 10$ 的数据集，你将获得 $2$ 分。 ### 样例解释 1 考虑处理第一次询问。你需要对 $A = (1,0,0,2)$ 求解。 在这种情况下，以下操作可以得到最优值 $1$： - 选择 $x=3$，站在位置 $3$。 - 移动到位置 $4$，给第 $4$ 个人一个糖果。 - 再次停在位置 $4$，再给第 $4$ 个人一个糖果。 - 操作结束。此时 $B = (0,0,0,2)$。 # 约束条件 - $1 \leq N \leq 10^5$ - $1 \leq Q \leq 10^5$ - $0 \leq A_i \leq 10^9$ - $1 \leq i \leq N$ - $0 \leq v \leq 10^9$ - 所有输入值均为整数。 由 ChatGPT 5 翻译