Usual Color Ball Problems

题目描述

你被给定正整数 $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$ 个与序列最前面球颜色相同的球，就把最前面的球放入该盒子。 如果不存在这样的盒子， 如果存在空盒子，就把最前面的球放入编号最小的那个盒子。 如果没有空盒子，就吃掉最前面的球，不把它放入任何盒子。

输入格式

输入按标准输入给出，格式如下： $N$ $M$ $K$ $C_1$ $C_2$ $\ldots$ $C_N$

输出格式

对每个 $r = 0, 1, 2, \ldots, N-1$，逐行输出问题的答案 $X_r$，格式如下： $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

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 \leq N \leq 2 \times 10^5$ $1 \leq M, K \leq N$ $1 \leq C_i \leq N$例如，下面说明 $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$。

标签: AtCoder|abc337F

来源

AtCoder|abc337F