← 返回题目列表

Codeforces · 1418/D

D. 垃圾问题

中文机器翻译题面 查看原题

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$$$ 中删除一堆,则 $$$1$$$ 是 $$$1$$$如果你需要在坐标$$$x_i$$$上添加一堆。保证对于 $$$t_i = 0$$$ 在当前的桩集中有这样的桩,而对于 $$$t_i = 1$$$ 在当前的桩集中不存在这样的桩。

输出

打印 $$$q+1$$$ 整数:Vova 在第一个查询之前和每个 $$$q$$$ 查询之后需要进行总清理的最小移动次数。

示例

输入 #1

5 6
1 2 6 8 10
1 4
1 9
0 6
0 10
1 100
1 50

输出 #1

5
7
7
5
4
8
49

输入 #2

5 8
5 1 2 4 3
0 1
0 2
0 3
0 4
0 5
1 1000000000
1 1
1 500000000

输出 #2

3
2
1
0
0
0
0
0
499999999

注意

考虑第一个例子。

最初,桩组是 $$$[1, 2, 6, 8, 10]$$$。第一个查询之前的答案是 $$$5$$$,因为您可以通过一次移动将所有桩从 $$$1$$$ 移动到 $$$2$$$,通过 $$$2$$$ 移动将所有桩从 $$$10$$$ 移动到 $$$8$$$,通过 $$$2$$$ 移动将所有桩从 $$$6$$$ 移动到 $$$8$$$。

第一次查询后,集合变为 $$$[1, 2, 4, 6, 8, 10]$$$。那么答案是 $$$7$$$ 因为您可以通过 $$$2$$$ 移动将所有桩从 $$$6$$$ 移动到 $$$4$$$,通过 $$$2$$$ 移动将所有桩从 $$$4$$$ 移动到 $$$2$$$,通过 $$$1$$$ 移动从 $$$2$$$ 到 $$$1$$$ 的所有桩以及从 $$$10$$$ 移动的所有桩$$$8$$$ 移动 $$$2$$$。

第二次查询后,桩组变为$$$[1, 2, 4, 6, 8, 9, 10]$$$,答案相同(并且之前的移动顺序可以应用于当前桩组)。

在第三次查询之后,这组桩变成 $$$[1, 2, 4, 8, 9, 10]$$$,答案是 $$$5$$$,因为你可以通过 $$$1$$$ 移动将所有桩从 $$$1$$$ 移动到 $$$2$$$,将所有桩从 $$$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$$$。