分数: 400 分
问题陈述
Takahashi 想要从整数多重集(可以包含相同值的多个副本的集合)中重复添加和删除元素,并计算有多少个删除满足特定条件。
最初,多重集是空的。你被给予 Q 按顺序查询以下内容 2 类型。让 X_i 表示由 i第一个查询。
+X_i:添加该值的一份副本 X_i 到多重集。-X_i:删除该值的一份副本 来自多重集的 X_i 。保证该值至少有一份副本 此时多重集中存在 X_i 。
对于删除查询,如果值 X_i 被删除 匹配删除之前多重集的中位数,此删除称为“中值命中”。
这里,多重集的中位数 n 元素 (n \geq 1) 定义如下:当所有元素按升序排序时, \lceil n/2 \rceil第一个值(1 索引)是中位数。也就是说,当元素个数为奇数时,为中间值;当偶数时,它是两个中间值中较小的一个。
由于多重集在删除查询时至少包含一个元素,因此中位数始终是明确定义的。
按顺序处理所有查询并确定“中值命中”发生的次数。
约束
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq X_i \leq 10^9
- 当时
-X_i 查询已给出,至少一份值 X_i 存在于多重集中。 - 输入中给出的所有数值均为整数。
输入
输入是从标准输入按以下格式给出的:
Q Query_1 Query_2 \vdots Query_Q
每个 Query_i (1 \leq i \leq Q) 的格式为 + X_i or - X_i,其中代表查询类型的字符 (+ or -) 和正整数 X_i 用空格分隔。
输出
输出“中值命中”发生的次数,作为一行上的单个整数。
示例输入 1
6 + 1 + 3 + 2 - 2 - 1 - 3
示例输出 1
3
示例输入 2
8 + 10 + 20 - 20 + 15 + 25 - 25 - 10 - 15
示例输出 2
2
示例输入 3
15 + 5 + 1 + 5 + 3 + 3 - 3 + 4 - 5 + 2 - 3 + 5 - 4 - 5 - 1 - 2
示例输出 3
4
示例输入 4
25 + 1000000000 + 7 + 7 + 500 + 8 - 7 + 6 - 8 + 9 + 10 - 7 + 9 - 9 + 1 - 6 + 2 + 3 - 9 + 4 - 4 - 1000000000 - 3 - 1 - 10 - 2
示例输出 4
7
示例输入 5
1 + 1000000000
示例输出 5
0