CF2025G Variable Damage

Monocarp 正在召集一支军队，在一款电子游戏中与一条龙作战。 军队由两部分组成：英雄和防御神器。每个英雄有一个参数——他的生命值。每个防御神器也有一个参数——它的耐久度。 在战斗开始前，Monocarp 会将神器分配给英雄，使得每个英雄最多只能获得一个神器。 战斗由若干回合组成，每回合流程如下： - 首先，龙会对每个英雄造成 $ \frac{1}{a + b} $ 的伤害（为实数，不进行取整），其中 $ a $ 表示当前存活的英雄数量，$ b $ 表示当前激活的神器数量； - 然后，所有生命值小于等于 $ 0 $ 的英雄死亡； - 最后，部分神器会失效。若某个神器的耐久度为 $ x $，当持有该神器的英雄死亡，或该英雄自战斗开始累计受到 $ x $ 点伤害时，该神器会失效。如果神器没有被任何英雄持有，则从战斗开始就处于失效状态。 当没有英雄存活时，战斗结束。 最初，军队为空。共有 $ q $ 次操作，每次操作可以向军队中添加一个生命值为 $ x $ 的英雄，或添加一个耐久度为 $ y $ 的神器。每次操作后，请你输出在最优分配神器的情况下，Monocarp 最多能坚持多少回合。

第一行包含一个整数 $ q $（$ 1 \le q \le 3 \cdot 10^5 $），表示操作次数。 接下来 $ q $ 行，每行包含两个整数 $ t_i $ 和 $ v_i $（$ t_i \in \{1, 2\} $，$ 1 \le v_i \le 10^9 $），表示第 $ i $ 次操作的类型和参数。若 $ t_i = 1 $，则添加一个生命值为 $ v_i $ 的英雄；若 $ t_i = 2 $，则添加一个耐久度为 $ v_i $ 的神器。

输出 $ q $ 个整数。每次操作后，输出在最优分配神器的情况下，Monocarp 最多能坚持的回合数。

我们来看第一个样例。 - 首先添加了一个耐久度为 $ 5 $ 的神器。由于还没有英雄，战斗立即结束。 - 添加了一个生命值为 $ 4 $ 的英雄。Monocarp 可以给他分配耐久度为 $ 5 $ 的神器。此时，每回合英雄受到 $ \frac{1}{1 + 1} = \frac{1}{2} $ 的伤害。经过 $ 8 $ 回合后，英雄累计受到 $ 4 $ 点伤害而死亡，神器也随之失效。没有英雄存活，战斗结束，总共进行了 $ 8 $ 回合。 - 添加了一个生命值为 $ 10 $ 的英雄。现在可以将耐久度为 $ 5 $ 的神器分配给这个英雄。前 $ 12 $ 回合，两个英雄每回合受到 $ \frac{1}{2 + 1} = \frac{1}{3} $ 的伤害，第一个英雄累计受到 $ 4 $ 点伤害后死亡，第二个英雄还剩 $ 6 $ 点生命值，神器还剩 $ 1 $ 点耐久度。此时每回合伤害变为 $ \frac{1}{2} $，再经过 $ 2 $ 回合神器失效，第二个英雄还剩 $ 5 $ 点生命值。再经过 $ 5 $ 回合，第二个英雄死亡。最终答案为 $ 12 + 2 + 5 = 19 $。 由 ChatGPT 4.1 翻译