Subset Trick
题意翻译
Vanya 有一个初始大小为 $n$ 的集合 $S$ 和 $q$ 次往集合加数/删数的操作。
称一个 $x$ 为不合适的,当前仅当满足可以取出 $S$ 的两个 **大小相同** 的子集,其中一个和 $\le x$,另一个和 $>x$。
求初始集合与每次操作结束后的集合不合适的 $x$ 的数量。
题目描述
Vanya invented an interesting trick with a set of integers.
Let an illusionist have a set of positive integers $ S $ . He names a positive integer $ x $ . Then an audience volunteer must choose some subset (possibly, empty) of $ S $ without disclosing it to the illusionist. The volunteer tells the illusionist the size of the chosen subset. And here comes the trick: the illusionist guesses whether the sum of the subset elements does not exceed $ x $ . The sum of elements of an empty subset is considered to be $ 0 $ .
Vanya wants to prepare the trick for a public performance. He prepared some set of distinct positive integers $ S $ . Vasya wants the trick to be successful. He calls a positive number $ x $ unsuitable, if he can't be sure that the trick would be successful for every subset a viewer can choose.
Vanya wants to count the number of unsuitable integers for the chosen set $ S $ .
Vanya plans to try different sets $ S $ . He wants you to write a program that finds the number of unsuitable integers for the initial set $ S $ , and after each change to the set $ S $ . Vanya will make $ q $ changes to the set, and each change is one of the following two types:
- add a new integer $ a $ to the set $ S $ , or
- remove some integer $ a $ from the set $ S $ .
输入输出格式
输入格式
The first line contains two integers $ n $ , $ q $ ( $ 1 \leq n, q \leq 200\,000 $ ) — the size of the initial set $ S $ and the number of changes.
The next line contains $ n $ distinct integers $ s_1, s_2, \ldots, s_n $ ( $ 1 \leq s_i \leq 10^{13} $ ) — the initial elements of $ S $ .
Each of the following $ q $ lines contain two integers $ t_i $ , $ a_i $ ( $ 1 \leq t_i \leq 2 $ , $ 1 \leq a_i \leq 10^{13} $ ), describing a change:
- If $ t_i = 1 $ , then an integer $ a_i $ is added to the set $ S $ . It is guaranteed that this integer is not present in $ S $ before this operation.
- If $ t_i = 2 $ , then an integer $ a_i $ is removed from the set $ S $ . In is guaranteed that this integer is present in $ S $ before this operation.
输出格式
Print $ q + 1 $ lines.
In the first line print the number of unsuitable integers for the initial set $ S $ . In the next $ q $ lines print the number of unsuitable integers for $ S $ after each change.
输入输出样例
输入样例 #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
说明
In the first example the initial set is $ S = \{1, 2, 3\} $ . For this set the trick can be unsuccessful for $ x \in \{1, 2, 3, 4\} $ . For example, if $ x = 4 $ , the volunteer can choose the subset $ \{1, 2\} $ with sum $ 3 \leq x $ , and can choose the subset $ \{2, 3\} $ with sum $ 5 > x $ . However, in both cases the illusionist only know the same size of the subset ( $ 2 $ ), so he can't be sure answering making a guess. Since there is only one subset of size $ 3 $ , and the sum of each subset of smaller size does not exceed $ 5 $ , all $ x \ge 5 $ are suitable.