← 返回题目列表

AtCoder · abc337_f

I. 常见的色球问题

中文机器翻译题面 查看原题

分数: 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