Score: $550$ points

问题描述

你已知正整数 $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$。另外，还有编号为 $1$ 到 $M$ 的 $M$ 个空盒子。

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

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

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

• 然后，在序列中至少还有一个球的情况下，重复以下操作。

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

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 01:28:23