AT_past17_o 整地クエリ

给你一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。我们对该序列定义如下操作： - 操作：选择 $A$ 的一个元素，加 $1$ 或减 $1$。 给你 $Q$ 个查询，按给定顺序处理。每个查询有以下两种类型之一： - `1 k d`：将 $d$ 加到 $A_k$ 上（其中 $d$ 是 $1$ 或 $-1$）。 - `2 x`：求使 $A$ 的所有元素都变为 $x$ 所需的最少操作次数。实际操作不执行。

输入通过标准输入给出，格式如下： > $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$ 这里，$\mathrm{query}_i$ 表示第 $i$ 个查询，格式如下二选一： > $1$ $k$ $d$ > $2$ $x$

输出 $q$ 行，其中 $q$ 是第 $2$ 种类型查询的数量。第 $j$ 行（$1\leq j\leq q$）应输出第 $j$ 次第 $2$ 种类型查询的答案。

### 样例说明 1 初始时，$A = (3, 5, 7, 2)$。 - 第 $1$ 个查询中，最优做法是给 $A_1$ 加 $1$ 一次，给 $A_2$ 减 $1$ 一次，给 $A_3$ 减 $1$ 三次，给 $A_4$ 加 $1$ 两次。因此总步数为 $1+1+3+2=7$，应输出 $7$。 - 第 $2$ 个查询，给 $A_1$ 加 $1$。此时 $A=(4,5,7,2)$。 - 第 $3$ 个查询，给 $A_2$ 减 $1$。此时 $A=(4,4,7,2)$。 - 第 $4$ 个查询，最优做法是对 $A_3$ 减 $1$ 三次，对 $A_4$ 加 $1$ 两次。因此总步数为 $3+2=5$，应输出 $5$。 ### 数据范围 - 所有输入值均为整数。 - $1 \leq N,Q \leq 2\times 10^5$ - $|A_i| \leq 10^9$ - 对于每个第 $1$ 种类型的查询，$1 \leq k \leq N$。 - 每个第 $1$ 种类型的查询中，$d$ 为 $1$ 或 $-1$。 - 每个第 $2$ 种类型的查询中，$|x| \leq 10^9$。 - 至少有一个第 $2$ 种类型的查询。 由 ChatGPT 5 翻译