CF1418D Trash Problem

Vova 决定打扫他的房间。房间可以用坐标轴 $OX$ 表示。房间里有 $n$ 堆垃圾，第 $i$ 堆垃圾的坐标为整数 $p_i$。所有垃圾堆的坐标都不相同。 我们定义一次“完全清理”为如下过程。该过程的目标是将所有垃圾堆集中到不超过两个不同的 $x$ 坐标上。为实现这一目标，Vova 可以进行若干次（可能为零次）移动。每次移动时，他可以选择某个 $x$，并用扫帚将所有位于 $x$ 的垃圾堆移动到 $x+1$ 或 $x-1$。注意，他不能选择只移动部分垃圾堆。 此外，有两种类型的操作： - $0\ x$ —— 从坐标 $x$ 移除一堆垃圾。保证此时坐标 $x$ 上有一堆垃圾。 - $1\ x$ —— 在坐标 $x$ 添加一堆垃圾。保证此时坐标 $x$ 上没有垃圾堆。 注意，某些时刻房间里可能没有任何垃圾堆。 Vova 想知道，在每次操作前和每次操作后，他最少需要多少次移动才能完成一次完全清理。操作按给定顺序依次进行。注意，完全清理只是用于计算最少移动次数，实际并不会改变垃圾堆的状态。 为便于理解，请阅读下方的提示部分，查看第一个样例的详细解释。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 10^5$），分别表示初始垃圾堆的数量和操作的数量。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le 10^9$），其中 $p_i$ 表示第 $i$ 堆垃圾的坐标。 接下来的 $q$ 行描述了每个操作。第 $i$ 个操作由两个整数 $t_i$ 和 $x_i$ 组成（$0 \le t_i \le 1; 1 \le x_i \le 10^9$），其中 $t_i = 0$ 表示需要从坐标 $x_i$ 移除一堆垃圾，$t_i = 1$ 表示需要在坐标 $x_i$ 添加一堆垃圾。保证对于 $t_i = 0$，当前垃圾堆集合中存在 $x_i$，对于 $t_i = 1$，当前垃圾堆集合中不存在 $x_i$。

输出 $q+1$ 个整数，依次表示在第一次操作前以及每次操作后，Vova 完成一次完全清理所需的最少移动次数。

以第一个样例为例说明。 初始垃圾堆集合为 $[1, 2, 6, 8, 10]$。此时答案为 $5$，因为可以将 $1$ 移动到 $2$（1 次），将 $10$ 移动到 $8$（2 次），将 $6$ 移动到 $8$（2 次）。 第一次操作后，垃圾堆集合变为 $[1, 2, 4, 6, 8, 10]$。此时答案为 $7$，因为可以将 $6$ 移动到 $4$（2 次），$4$ 移动到 $2$（2 次），$2$ 移动到 $1$（1 次），$10$ 移动到 $8$（2 次）。 第二次操作后，垃圾堆集合为 $[1, 2, 4, 6, 8, 9, 10]$，答案与上一次相同（可以使用上一次的移动方案）。 第三次操作后，垃圾堆集合为 $[1, 2, 4, 8, 9, 10]$，此时答案为 $5$，因为可以将 $1$ 移动到 $2$（1 次），$2$ 移动到 $4$（2 次），$10$ 移动到 $9$（1 次），$9$ 移动到 $8$（1 次）。 第四次操作后，垃圾堆集合为 $[1, 2, 4, 8, 9]$，答案几乎相同（可以不再移动 $10$ 处的垃圾堆）。 第五次操作后，垃圾堆集合为 $[1, 2, 4, 8, 9, 100]$。可以将 $1$ 及之后的垃圾堆全部移动到 $9$，$100$ 保持不动，答案为 $8$。 第六次操作后，垃圾堆集合为 $[1, 2, 4, 8, 9, 50, 100]$。此时答案为 $49$，方案与上一次几乎相同，只需将 $50$ 也移动到 $9$。 由 ChatGPT 4.1 翻译