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 翻译