#P7216. [2023省队模拟]破解密码
[2023省队模拟]破解密码
题目描述
Alice 维护一个整数集合 。对于一个整数 ,如果存在两个子集 ,满足
$$|S|=|T|,\qquad \operatorname{Sum}(S)\le p,\qquad \operatorname{Sum}(T)\ge p+1,$$就称 是当前集合的一个可能密码。其中 是 内元素之和。 只需满足上述条件,可以相交。
Alice 每次向集合加入一个元素,或从集合中删除一个元素。求初始状态及每次修改后可能密码的个数。空集合允许出现,此时没有可能密码。
输入格式
第一行两个整数 ,分别表示初始集合的大小和修改次数。
第二行 个整数,描述初始集合。
接下来 行,每行两个整数 。若 ,将 加入集合,否则从集合删除 。保证加入的元素原先不在集合中,删除的元素原先在集合中。
输出格式
输出 行,每行一个整数。第一行表示初始集合的答案,之后第 行表示第 次修改后的答案。
样例输入 1
1 7
5
1 6
0 6
1 9
1 7
0 5
0 9
0 7
样例输出 1
0
1
0
4
8
2
0
0
样例输入 2
6 8
8 3 6 1 7 4
0 6
1 6
1 2
0 1
1 9
0 8
1 1
0 9
样例输出 2
27
21
27
29
26
35
27
30
21
数据范围与约定
对于所有数据,。初始集合的元素与修改参数 均为正整数。程序须支持这些值达到 。原 PDF 的范围表述为 ,本站原始测试中存在略大于 的初始元素,所以上界按原生成程序可能生成的范围给出。集合中任意时刻的元素互不相同。
| 子任务 | 限制 | 本站分值 |
|---|---|---|
| 1 | 20 | |
| 2 | ||
| 3 | ||
| 4 | 没有删除操作 | |
| 5 | 无特殊限制 |