103375: [Atcoder]ABC337 F - Usual Color Ball Problems

Problem Statement

You are given positive integers $N$, $M$, $K$, and a sequence of positive integers of length $N$, $(C_1, C_2, \ldots, C_N)$. For each $r = 0, 1, 2, \ldots, N-1$, print the answer to the following problem.

There is a sequence of $N$ colored balls. For $i = 1, 2, \ldots, N$, the color of the $i$-th ball from the beginning of the sequence is $C_i$. Additionally, there are $M$ empty boxes numbered $1$ to $M$.

Determine the total number of balls in the boxes after performing the following steps.

• First, perform the following operation $r$ times.

  • Move the frontmost ball in the sequence to the end of the sequence.

• Then, repeat the following operation as long as at least one ball remains in the sequence.

  • If there is a box that already contains at least one but fewer than $K$ balls of the same color as the frontmost ball in the sequence, put the frontmost ball into that box.
  • If there is no such box,
    • If there is an empty box, put the frontmost ball into the one with the smallest box number.
    • If there are no empty boxes, eat the frontmost ball without putting it into any box.

Constraints

• All input values are integers.
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M, K \leq N$
• $1 \leq C_i \leq N$

Input

The input is given from Standard Input in the following format:

$N$ $M$ $K$
$C_1$ $C_2$ $\ldots$ $C_N$

Output

Print the answer $X_r$ to the problem for each $r = 0, 1, 2, \ldots, N-1$ over $N$ lines as follows:

$X_0$
$X_1$
$\vdots$
$X_{N-1}$

Sample Input 1

7 2 2
1 2 3 5 2 5 4

Sample Output 1

3
3
3
4
4
3
2

For example, let us explain the procedure for $r = 1$. First, perform the operation "Move the frontmost ball in the sequence to the end of the sequence" once, and the sequence of ball colors becomes $(2, 3, 5, 2, 5, 4, 1)$. Then, proceed with the operation of putting balls into boxes as follows:

• First operation: The color of the frontmost ball is $2$. There is no box with at least one but fewer than two balls of color $2$, so put the frontmost ball into the empty box with the smallest box number, box $1$.
• Second operation: The color of the frontmost ball is $3$. There is no box with at least one but fewer than two balls of color $3$, so put the frontmost ball into the empty box with the smallest box number, box $2$.
• Third operation: The color of the frontmost ball is $5$. There is no box with at least one but fewer than two balls of color $5$ and no empty boxes, so eat the frontmost ball.
• Fourth operation: The color of the frontmost ball is $2$. There is a box, box $1$, with at least one but fewer than two balls of color $2$, so put the frontmost ball into box $1$.
• Fifth operation: The color of the frontmost ball is $5$. There is no box with at least one but fewer than two balls of color $5$ and no empty boxes, so eat the frontmost ball.
• Sixth operation: The color of the frontmost ball is $4$. There is no box with at least one but fewer than two balls of color $4$ and no empty boxes, so eat the frontmost ball.
• Seventh operation: The color of the frontmost ball is $1$. There is no box with at least one but fewer than two balls of color $1$ and no empty boxes, so eat the frontmost ball.

The final total number of balls in the boxes is $3$, so the answer to the problem for $r = 1$ is $3$.

Sample Input 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

Sample Output 2

14
14
14
14
13
13
13
11
8
9
9
11
13
14
14
14
14
14
14
13

问题描述

给你四个正整数 $N$、$M$、$K$ 和长度为 $N$ 的正整数序列 $(C_1, C_2, \ldots, C_N)$。对于 $r = 0, 1, 2, \ldots, N-1$，请输出以下问题的答案。

有 $N$ 个彩球组成的序列。对于 $i = 1, 2, \ldots, N$，从序列开始的第 $i$ 个球的颜色是 $C_i$。 此外，还有 $M$ 个编号为 $1$ 到 $M$ 的空盒子。

执行以下步骤后，确定盒子里总共有多少个球。

• 首先，执行以下操作 $r$ 次。

  • 将序列中最前面的球移到序列的末尾。

• 然后，只要序列中至少还有一个球，就重复执行以下操作。

  • 如果有一个盒子已经至少有一个但不到 $K$ 个与序列最前面的球颜色相同的球，将最前面的球放入那个盒子中。
  • 如果没有这样的盒子，
    • 如果有空盒子，将最前面的球放入编号最小的空盒子中。
    • 如果没有空盒子，不将最前面的球放入任何盒子中，直接吃掉它。

限制条件

• 所有输入值都是整数。
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M, K \leq N$
• $1 \leq C_i \leq N$

输入

输入从标准输入以以下格式给出：

$N$ $M$ $K$
$C_1$ $C_2$ $\ldots$ $C_N$

输出

在 $N$ 行中，按以下格式分别输出对于每个 $r = 0, 1, 2, \ldots, N-1$ 的问题答案 $X_r$：

$X_0$
$X_1$
$\vdots$
$X_{N-1}$

样例输入 1

7 2 2
1 2 3 5 2 5 4

样例输出 1

3
3
3
4
4
3
2

例如，让我们解释 $r = 1$ 的过程。 首先，执行一次操作“将序列中最前面的球移到序列的末尾”，彩球序列变为 $(2, 3, 5, 2, 5, 4, 1)$。 然后，按照以下顺序将球放入盒子中：

• 第一次操作：最前面的球颜色为 $2$。没有一个盒子至少有一个但不到两个颜色为 $2$ 的球，因此将最前面的球放入编号最小的空盒子，即盒子 $1$。
• 第二次操作：最前面的球颜色为 $3$。没有一个盒子至少有一个但不到两个颜色为 $3$ 的球，因此将最前面的球放入编号最小的空盒子，即盒子 $2$。
• 第三次操作：最前面的球颜色为 $5$。没有一个盒子至少有一个但不到两个颜色为 $5$ 的球，并且没有空盒子，因此吃掉最前面的球。
• 第四次操作：最前面的球颜色为 $2$。有一个盒子，即盒子 $1$，至少有一个但不到两个颜色为 $2$ 的球，因此将最前面的球放入盒子 $1$。
• 第五次操作：最前面的球颜色为 $5$。没有一个盒子至少有一个但不到两个颜色为 $5$ 的球，并且没有空盒子，因此吃掉最前面的球。
• 第六次操作：最前面的球颜色为 $4$。没有一个盒子至少有一个但不到两个颜色为 $4$ 的球，并且没有空盒子，因此吃掉最前面的球。
• 第七次操作：最前面的球颜色为 $1$。没有一个盒子至少有一个但不到两个颜色为 $1$ 的球，并且没有空盒子，因此吃掉最前面的球。

最终，盒子里总共有 $3$ 个球，所以 $r = 1$ 的问题答案为 $3$。

样例输入 2

20 5 4
20 2 20 2 7 3 11 20 3 8 7 9 1 11 8 20 2 18 11 18

样例输出 2

14
14
14
14
13
13
13
11
8
9
9
11
13
14
14
14
14
14
14
13