常见的彩球问题

题目描述

给定正整数 $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$ 次:

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

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

• 如果存在一个箱子，其中装有至少 1 个但少于 $K$ 个与序列中最前面的球同色的球，将最前面的球放入该箱子。
• 如果不存在这样的箱子:
  • 如果有空箱子，将最前面的球放入编号最小的空箱子。
  • 如果没有空箱子，吃掉最前面的球，不放入任何箱子。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

对于每个 $r=0, 1, 2, \ldots, N-1$，将问题的答案 $X_r$ 输出在 $N$ 行上，如下所示:

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

样例

7 2 2
1 2 3 5 2 5 4

3
3
3
4
4
3
2

例如，说明 $r=1$ 时的过程。 首先，执行一次「将序列中最前面的球移到序列末尾」的操作，球的颜色序列变为 $(2, 3, 5, 2, 5, 4, 1)$。 然后，按如下方式进行把球放入箱子的操作:

• 第 1 次操作：最前面的球颜色是 2。不存在装有至少 1 个但少于 2 个颜色为 2 的球的箱子，因此将最前面的球放入编号最小的空箱子——箱子 1。
• 第 2 次操作：最前面的球颜色是 3。不存在装有至少 1 个但少于 2 个颜色为 3 的球的箱子，因此将最前面的球放入编号最小的空箱子——箱子 2。
• 第 3 次操作：最前面的球颜色是 5。不存在装有至少 1 个但少于 2 个颜色为 5 的球的箱子，且没有空箱子，因此吃掉最前面的球。
• 第 4 次操作：最前面的球颜色是 2。存在装有至少 1 个但少于 2 个颜色为 2 的球的箱子——箱子 1，因此将最前面的球放入箱子 1。
• 第 5 次操作：最前面的球颜色是 5。不存在装有至少 1 个但少于 2 个颜色为 5 的球的箱子，且没有空箱子，因此吃掉最前面的球。
• 第 6 次操作：最前面的球颜色是 4。不存在装有至少 1 个但少于 2 个颜色为 4 的球的箱子，且没有空箱子，因此吃掉最前面的球。
• 第 7 次操作：最前面的球颜色是 1。不存在装有至少 1 个但少于 2 个颜色为 1 的球的箱子，且没有空箱子，因此吃掉最前面的球。

最后箱子中球的总数是 3，所以 $r=1$ 时问题的答案是 3。

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

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

数据范围

• 所有输入值均为整数。
• $1 \le N \le 2 \times 10^5$
• $1 \le M, K \le N$
• $1 \le C_i \le N$