← 返回题目列表

Codeforces · 1500/E

E. 子集技巧

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

Vanya 用一组整数发明了一个有趣的技巧。

让一个魔术师有一组正整数$$$S$$$。他命名了一个正整数$$$x$$$。然后,观众志愿者必须选择 $$$S$$$ 的某个子集(可能是空的),而不将其透露给魔术师。志愿者告诉魔术师所选子集的大小。技巧来了:魔术师猜测子集元素的总和是否不超过$$$x$$$。空子集的元素总和被认为是$$$0$$$。

Vanya 想要为公开表演准备这个戏法。他准备了一组不同的正整数$$$S$$$。瓦夏希望诡计成功。如果他不能确定该技巧对于观看者可以选择的每个子集都会成功,那么他认为正数 $$$x$$$ 是不合适的。

Vanya 想要计算所选集合 $$$S$$$ 中不合适的整数的数量。

Vanya 计划尝试不同的组合 $$$S$$$。他希望你编写一个程序,找出初始集合 $$$S$$$ 以及每次更改集合 $$$S$$$ 后不合适的整数的数量。 Vanya 将对集合进行 $$$q$$$ 更改,每次更改都是以下两种类型之一:

- 将新整数 $$$a$$$ 添加到集合 $$$S$$$ 中,或者
- 从集合 $$$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$$$,则从集合 $$$S$$$ 中删除整数 $$$a_i$$$。保证在此操作之前该整数存在于 $$$S$$$ 中。

输出

打印 $$$q + 1$$$ 行。

在第一行中打印初始集合 $$$S$$$ 不合适的整数的数量。在接下来的 $$$q$$$ 行中,每次更改后打印 $$$S$$$ 不合适的整数的数量。

示例

输入 #1

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

输出 #1

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 \ge 5$$$ 都是合适的。