分数: 550 点
问题陈述
给你正整数 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 to 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
输出
打印答案 X_r 针对每个问题 r = 0, 1, 2, \ldots, N-1 结束 N 行如下:
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,所以将最前面的球放入盒子编号最小的空盒子中,box 1.
- 第二次操作:最前面的球的颜色是 3。没有盒子里至少有一个但少于两个色球 3,所以将最前面的球放入盒子编号最小的空盒子中,box 2.
- 第三次操作:最前面的球的颜色是 5。没有盒子里至少有一个但少于两个色球 5 并且没有空盒子,所以吃掉最前面的球。
- 第四次操作:最前面的球的颜色是 2。有一个盒子,盒子 1,至少有一个但少于两个色球 2,所以将最前面的球放入盒子中 1.
- 第五次操作:最前面的球的颜色是 5。没有盒子里至少有一个但少于两个色球 5 并且没有空盒子,所以吃掉最前面的球。
- 第六次操作:最前面的球的颜色是 4。没有盒子里至少有一个但少于两个色球 4 并且没有空盒子,所以吃掉最前面的球。
- 第七次操作:最前面的球的颜色是 1。没有盒子里至少有一个但少于两个色球 1 并且没有空盒子,所以吃掉最前面的球。
盒子里的球的最终总数是 3,所以问题的答案为 r = 1 is 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