CF1098D Eels

Vasya 是一个非常喜欢鱼的人，他的父母在新年时送给了他一个水族箱。Vasya 并没有鱼类学的学位，所以他认为把新水族箱装满鳗鱼是个好主意。不幸的是，鳗鱼是食肉动物，因此 Vasya 决定了解一下这个想法有多危险。 当多条鳗鱼被放进同一个水族箱时，它们会互相争斗，直到只剩下一条鱼。每当两条鳗鱼争斗时，体型较大的会吃掉体型较小的（如果它们体重相等，也会有一条吃掉另一条）。具体来说，假设水族箱里最初有 $n$ 条鳗鱼，第 $i$ 条的体重为 $x_i$。那么它们之间会发生 $n-1$ 场战斗，最终只剩下一条鳗鱼。每当两条体重分别为 $a$ 和 $b$ 的鳗鱼（$a \le b$）争斗时，体重为 $a$ 的鳗鱼会被吃掉并从水族箱中消失，而体重为 $b$ 的鳗鱼体重会增加到 $a+b$。 当两条体重为 $a$ 和 $b$ 的鳗鱼（$a \le b$）争斗时，如果 $b \le 2a$，则这场战斗被认为是危险的。对于给定的一组鳗鱼，危险值定义为：如果将这些鳗鱼放入同一个水族箱中，可能发生的危险战斗的最大数量。 现在 Vasya 正在计划要往水族箱里放哪些鳗鱼。他有一个鳗鱼集合（初始为空）。他会对这个集合进行一系列操作。每次操作，他要么向集合中加入一条鳗鱼，要么从集合中移除一条鳗鱼。每次操作后，Vasya 都会询问你当前集合的危险值。

输入的第一行为一个整数 $q$（$1 \le q \le 500\,000$），表示 Vasya 进行的操作次数。接下来的 $q$ 行描述每次操作。每次操作有两种类型： - `+ x` 表示向集合中加入一条体重为 $x$ 的鳗鱼（$1 \le x \le 10^9$）。注意集合中可以有多条体重相同的鳗鱼。 - `- x` 表示从集合中移除一条体重为 $x$ 的鳗鱼，保证集合中一定存在一条体重为 $x$ 的鳗鱼。

对于每次操作，输出一个整数，表示当前鳗鱼集合的危险值。

在第三个样例中，所有操作完成后，鳗鱼集合为 $\{1, 1, 4\}$。对于这组鳗鱼，如果全部放入同一个水族箱，有多种可能的战斗顺序： - 体重为 4 的鳗鱼先吃掉一条体重为 1 的鳗鱼，然后再吃掉另一条体重为 1 的鳗鱼。在这种情况下，没有任何一场战斗是危险的。 - 体重为 1 的鳗鱼先吃掉另一条体重为 1 的鳗鱼，这场战斗是危险的。现在水族箱中剩下体重为 4 和 2 的两条鳗鱼，体重较大的吃掉较小的，这场战斗也是危险的。在这种情况下，危险战斗的总数为 2。 因此，这组鳗鱼的危险值为 2。 由 ChatGPT 4.1 翻译