#P7216. [2023省队模拟]破解密码

    ID: 7050 传统题 3000ms 512MiB 尝试: 7 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-区间合并对称性分析二分查找离散化普通线段树线段树上二分

[2023省队模拟]破解密码

题目描述

Alice 维护一个整数集合 UU。对于一个整数 pp,如果存在两个子集 S,T⊆US,T\subseteq U,满足

$$|S|=|T|,\qquad \operatorname{Sum}(S)\le p,\qquad \operatorname{Sum}(T)\ge p+1,$$

就称 pp 是当前集合的一个可能密码。其中 Sum⁡(S)\operatorname{Sum}(S) 是 SS 内元素之和。S,TS,T 只需满足上述条件,可以相交。

Alice 每次向集合加入一个元素,或从集合中删除一个元素。求初始状态及每次修改后可能密码的个数。空集合允许出现,此时没有可能密码。

输入格式

第一行两个整数 n,qn,q,分别表示初始集合的大小和修改次数。

第二行 nn 个整数,描述初始集合。

接下来 qq 行,每行两个整数 op,yop,y。若 op=1op=1,将 yy 加入集合,否则从集合删除 yy。保证加入的元素原先不在集合中,删除的元素原先在集合中。

输出格式

输出 q+1q+1 行,每行一个整数。第一行表示初始集合的答案,之后第 ii 行表示第 i−1i-1 次修改后的答案。

样例输入 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

数据范围与约定

对于所有数据,n,q≤2×105n,q\le2\times10^5。初始集合的元素与修改参数 yy 均为正整数。程序须支持这些值达到 1012+10610^{12}+10^6。原 PDF 的范围表述为 101210^{12},本站原始测试中存在略大于 101210^{12} 的初始元素,所以上界按原生成程序可能生成的范围给出。集合中任意时刻的元素互不相同。

子任务 限制 本站分值
1 n,q≤10n,q\le10 20
2 n,q≤100n,q\le100
3 n,q≤1000n,q\le1000
4 没有删除操作
5 无特殊限制

原 PDF 题面