CF1500E Subset Trick

Vanya 发明了一个有趣的整数集合魔术。 假设魔术师手中有一个正整数集合 $S$。他报出一个正整数 $x$。然后，观众志愿者需要从 $S$ 中选择一个子集（可以为空），但不告诉魔术师具体选了哪些数。志愿者只告诉魔术师所选子集的大小。此时，魔术师需要判断所选子集的元素和是否不超过 $x$。空集的元素和视为 $0$。 Vanya 想将这个魔术用于公开表演。他准备了一个由不同正整数组成的集合 $S$。Vanya 希望魔术能够成功。他称一个正整数 $x$ 为“不合适的”，如果他不能确保对于观众可能选择的每一个子集，魔术都能成功。 Vanya 想统计对于所选集合 $S$，有多少个不合适的整数。 Vanya 计划尝试不同的集合 $S$。他希望你编写一个程序，能够在初始集合 $S$ 以及每次对 $S$ 的修改后，计算不合适的整数个数。Vanya 会对集合 $S$ 进行 $q$ 次修改，每次修改有以下两种类型之一： - 向集合 $S$ 中添加一个新的整数 $a$； - 从集合 $S$ 中移除某个整数 $a$。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 200\,000$），分别表示初始集合 $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$，则将整数 $a_i$ 从集合 $S$ 中移除。保证该整数在操作前在 $S$ 中。

输出 $q+1$ 行。 第一行输出初始集合 $S$ 的不合适整数个数。接下来的 $q$ 行，每行输出每次修改后集合 $S$ 的不合适整数个数。

在第一个样例中，初始集合为 $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 \ge 5$ 都是合适的。 由 ChatGPT 4.1 翻译