#10697. D - Strange Balls 奇怪的求 比赛编号240

D - Strange Balls 奇怪的求 比赛编号240

问题描述

Takahashi 有 N 个球。每个球上都有一个不小于 2 的整数 a_i。他将这些球一个接一个地插入一个圆柱体中。

这些球由特殊材料制成。当有 k 个球(k ≥ 2)上面写着相同的数字 k 时,这些球会消失。

对于每个 i1 ≤ i ≤ N),求在插入第 i 个球后圆柱体中剩余的球的数量。

输入

输入的格式如下:

N
a_1
a_2
…
a_N

其中:

  • N:球的数量。
  • a_i:第 i 个球上写的数字。

输出

输出 N 行,第 i 行表示在插入第 i 个球后,圆柱体中剩余的球的数量。

限制

  • 1 ≤ N ≤ 2 × 10^5
  • 2 ≤ a_i ≤ 2 × 10^51 ≤ i ≤ N
  • 输入中的所有值都是整数。

样例输入 1

5
3 2 3 2 2

样例输出 1

1
2
3
4
3

解释​:

  • 插入第1个球后,圆柱体中只有一个球,内容是:3
  • 插入第2个球后,圆柱体中有两个球,内容是:3, 2
  • 插入第3个球后,圆柱体中有三个球,内容是:3, 2, 3
  • 插入第4个球后,圆柱体中有四个球,内容是:3, 2, 3, 2
  • 插入第5个球后,圆柱体中有五个球,内容是:3, 2, 3, 2, 2。此时,两个连续的数字 2 会消失,最终剩下的球是:3, 2, 3,共3个。

image

解题思路

  • 使用栈(Stack)来模拟圆柱体的插入与消失过程。
    • 每次插入球时,检查栈顶是否存在相同的球,并检查它们的数量是否足够消失。
    • 如果存在连续相同的球,数量达到该球的值 k 时,就将这些球从栈中移除。
    • 每次插入之后,我们可以直接输出当前栈中球的数量。