← 返回题目列表

Codeforces · 1098/D

D. 鳗鱼

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

Vasya 是个大鱼爱好者,新年父母送了他一个水族箱。 Vasya 没有鱼类学学位,因此他认为在新的水族馆里养鳗鱼是个好主意。不幸的是,鳗鱼是掠食者,所以瓦夏决定找出这个想法有多危险。

进入一个水族馆,鳗鱼互相争斗,直到只剩下一条鱼。当两条鳗鱼打架时,大的鳗鱼会吃掉较小的鳗鱼(如果它们的重量相等,那么其中一只仍然会吃掉另一只)。也就是说,让 $$$n$$$ 鳗鱼最初位于水族箱中,其中第 $$$i$$$ 的重量为 $$$x_i$$$。然后它们之间会发生 $$$n-1$$$ 战斗,结果只有一条鳗鱼能够幸存。在两条重量为 $$$a$$$ 和 $$$b$$$ 的鳗鱼的战斗中,其中 $$$a \le b$$$,重量为 $$$a$$$ 的鳗鱼将被吃掉并从水族箱中消失,而重量为 $$$b$$$ 的鳗鱼将增加其重量至 $$$a+b$$$。

两条重量为 $$$a$$$ 和 $$$b$$$ 的鳗鱼之间的战斗,其中 $$$a \le b$$$,如果 $$$b \le 2 a$$$ 则被认为是危险的。对于一组给定的鳗鱼,危险被定义为如果将它们放入一个水族箱中,这些鳗鱼之间可能发生的危险战斗的最大数量。

现在 Vasya 正在计划,他想将这些鳗鱼放入水族馆。他有一些鳗鱼(最初是空的)。他用这个集合做了一系列的操作。在每次操作中,他要么在集合中添加一条鳗鱼,要么从集合中删除一条鳗鱼。 Vasya 要求您在每次操作后计算当前一组鳗鱼的危险度。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500\,000$$$),即 Vasya 进行的操作数。接下来的 $$$q$$$ 行描述了操作。每个操作都有两种类型之一:

- + x 描述将一条重量为 $$$x$$$ 的鳗鱼添加到集合中 ($$$1 \le x \le 10^9$$$)。请注意,该组中可以有几条重量相同的鳗鱼。
- - x描述从一组中取出一条重量为$$$x$$$的鳗鱼,并保证该组中存在一条这样重量的鳗鱼。

输出

对于每个操作,输出单个整数,表示该操作后该组鳗鱼的危险程度。

示例

输入 #1

2
+ 1
- 1

输出 #1

0
0

输入 #2

4
+ 1
+ 3
+ 7
- 3

输出 #2

0
0
1
0

输入 #3

9
+ 2
+ 2
+ 12
- 2
- 2
+ 4
+ 1
+ 1
- 12

输出 #3

0
1
1
0
0
0
0
3
2

注意

在第三个示例中,执行完所有操作后,鳗鱼集看起来像 $$$\{1, 1, 4\}$$$。对于这组鳗鱼,如果将它们全部放入一个水族箱中,则有几种可能的情况:

- 重量为 4 的鳗鱼吃掉重量为 1 的鳗鱼,然后吃掉第二条重量为 1 的鳗鱼。在这种情况下,所有战斗都没有危险。
- 重量1的鳗鱼吃掉重量1的鳗鱼,这场战斗很危险。现在水族箱里有两条鳗鱼,它们的重量分别是4和2。大的吃小的,这场战斗也很危险。在这种情况下,危险战斗的总数将为2。

因此,这组鳗鱼的危险度为2。