← 返回题目列表

AtCoder · awc0055_d

D. 中值检查

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

分数: 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