[AdditionalFile5392.zip](file://AdditionalFile5392.zip?type=additional_file)

#5392. 「OOI 2021 Day 2」子集魔术

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2021 Day2 T4 「Фокус с подмножествами」。

瓦尼亚发明了一个有趣的整数集合魔术。

假设魔术师有一个正整数集合 $S$。他会说出一个正整数 $x$。观众需要选择一个 $S$ 的子集（可以是空集），但不能让魔术师看到。接着，观众告诉魔术师所选子集的大小。魔术的重点在于，魔术师随后需要猜出：所选子集的元素之和是否不超过 $x$。对于空集，假设其和为 $0$。

瓦尼亚非常喜欢这个魔术，因此开始准备向公众展示。为此，他准备了一个由不同正整数组成的集合 $S$。当然，瓦尼亚希望魔术一定能成功。他将一个正整数 $x$ 定义为失败的，如果他无法确定对于观众选择的任何子集，魔术都能成功。

为了评估他选择的集合 $S$ 的好坏，他想计算出对于该集合有多少个失败的正整数。

此外，瓦尼亚计划测试不同的集合 $S$。因此，他请求你编写一个程序，计算初始集合 $S$ 的失败正整数数量，以及每次修改后的集合 $S$ 的失败正整数数量。瓦尼亚将进行 $q$ 次集合修改，每次修改为以下两种操作之一：

• 在集合 $S$ 中添加一个新数字 $a$。
• 从集合 $S$ 中删除一个数字 $a$。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n, q \leq 200000)$，分别表示初始集合 $S$ 的大小和修改次数。

第二行包含 $n$ 个不同的整数 $s_1, s_2, \ldots, s_n$ $(1 \leq s_i \leq 10^{13})$，表示初始集合 $S$ 的元素。

接下来的 $q$ 行，每行包含两个整数 $t_i$ 和 $a_i$ $(1 \leq t_i \leq 2, 1 \leq a_i \leq 10^{13})$，描述一次修改操作。

• 如果 $t_i = 1$，则表示将新数字 $a_i$ 添加到集合 $S$ 中。保证在执行操作前，该数字不在集合 $S$ 中。
• 如果 $t_i = 2$，则表示从集合 $S$ 中删除数字 $a_i$。保证在执行操作前，该数字在集合 $S$ 中。

输出格式

输出 $q + 1$ 行。

第一行输出初始集合 $S$ 的失败正整数数量。接下来的 $q$ 行输出每次修改后集合 $S$ 的失败正整数数量。

样例

输入

3 11
1 2 3
2 1
1 5
1 6
1 7
2 6
2 2
2 3
1 10
2 5
2 7
2 10

输出

4
1
6
12
19
13
8
2
10
3
0
0

在第一个样例中，初始集合 $S = \{1, 2, 3\}$。对于这个集合，魔术在 $x \in \{1, 2, 3, 4\}$ 时可能失败。例如，若 $x = 4$，观众可以选择子集 $\{1, 2\}$，其和为 $3 \leq x$，也可以选择子集 $\{2, 3\}$，其和为 $5 > x$。但在这两种情况下，观众都会告诉魔术师子集大小为 $2$，因此魔术师无法准确判断。然而，由于大小为 $3$ 的子集是唯一的，且任何较小子集的和都不超过 $5$，所有 $x \geq 5$ 都不是失败的。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。