#2336. 「JOI 2017 Final」绳

内存限制:256 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOI 2017 Final T5「 / Rope

JOI 小宝宝正拿着一根绳子玩。绳子可视为一条长度为 N 的左右延伸的线段。绳子由 N 根线连接而成,每根线的长度为 1 ,厚度为 1 。绳子上的线共有 M 种颜色,左数第 i 根线 (1\leqslant i\leqslant N) 的颜色为 C_i(1\leqslant C_i\leqslant M) 绳子的左端点意为左数第 1 根线的左端点,绳子的右端点意为右数第 1 根线的右端点。显然左数第 i 根线 (1\leqslant i\leqslant N) 的右端点 到 绳子的左端点 的距离为 i

JOI 把绳子的长度缩短了。具体来说,JOI 反复地进行以下过程,直到绳长缩短至 2

  • 假设此时绳子的长度为 L 。指定一个整数 j(1\leqslant j<L) ,使绳子左数第 j 根线成为绳子的左端点(最左的线),并折叠绳子。也就是说,
    • 如果 j\leqslant \cfrac{L}{2} ,则将左数第 i 根线 (1\leqslant i\leqslant j) 与左数第 (2j-i+1) 根线拧成一股。此时,绳子原本的右端点仍是右端点,绳长变为 L-j
    • 如果 j> \cfrac{L}{2} ,则将左数第 i 根线 (2j-L+1\leqslant i\leqslant j) 与左数第 (2j-i+1) 根线拧成一股。此时,绳子原本的左端点变为右端点,绳长变为 j
  • 两条线的颜色相同才能拧成一股。在将两条线拧成一股前,可以任意改变线的颜色。将线染成其他颜色所需的费用 等于 线的厚度。颜色匹配后,两条线将被拧成一股,新的一股线的厚度 将为 两条线的厚度之和。

我们把绳长缩短至 2 的绳子称为最终的绳子。JOI 希望使得将绳长缩短至 2 所需的费用尽可能小。对于每种颜色,JOI 都想知道,在最终的绳子中包含这种颜色的情况下,将绳长缩短至 2 所需的最小费用。

你的任务是帮 JOI 解决这个问题。

输入格式

第一行有两个整数 N, M ,用空格分隔。
第二行有 N 个用空格分隔的整数 C_1, C_2, \ldots, C_N
输入的所有数的含义见题目描述。

输出格式

M 行,第 c (1\leqslant c\leqslant M) 有一个整数,表示在最终的绳子中包含颜色 c 的情况下,将绳长缩短至 2 所需的最小费用。

样例

输入样例 1

5 3
1 2 3 3 2

输出样例 1

2
1
1

样例解释 1

通过下述步骤,只需花费 2 ,就可以使得最终的绳子中包含颜色 1

  • 把左数第 2 根线染成颜色 1 。折叠绳子使得 原本到左端点的距离为 1 的端点 变为 新的左端点。现在,从左往右数,线的颜色依次是 1, 3, 3, 2 ,厚度依次是 2, 1, 1, 1
  • 把左数第 4 根线染成颜色 1 。折叠绳子使得 原本到左端点的距离为 2 的端点 变为 新的左端点。现在,从左往右数,线的颜色依次是 3, 1 ,厚度依次是 2, 3

通过下述步骤,只需花费 1 ,就可以使得最终的绳子中包含颜色 2 3

  • 折叠绳子使得 原本到左端点的距离为 3 的端点 变为 新的左端点。现在,从左往右数,线的颜色依次是 3, 2, 1 ,厚度依次是 2, 2, 1
  • 把左数第 3 根线染成颜色 2 。折叠绳子使得 原本到左端点的距离为 2 的端点 变为 新的左端点。现在,从左往右数,线的颜色依次是 2, 3 ,厚度依次是 3, 2

输入样例 2

7 3
1 2 2 1 3 3 3

输出样例 2

2
2
2

样例解释 2

通过下述步骤,只需花费 2 ,就可以使得最终的绳子中包含颜色 1

  • 折叠绳子使得 原本到左端点的距离为 2 的端点 变为 新的左端点。
  • 把左数第 1 根线染成颜色 1 。折叠绳子使得 原本到左端点的距离为 1 的端点 变为 新的左端点。注意这次染色的费用为 2 ,因为此时左数第 1 根线的厚度为 2
  • 折叠绳子使得 原本到左端点的距离为 3 的端点 变为 新的左端点。
  • 折叠绳子使得 原本到左端点的距离为 1 的端点 变为 新的左端点。

输入样例 3

10 3
2 2 1 1 3 3 2 1 1 2

输出样例 3

3
3
4

数据范围与提示

对于 15\% 的数据, N\leqslant 15, M\leqslant 10
对于另外 30\% 的数据, N\leqslant 10^5, M\leqslant 10
对于另外 10\% 的数据, N\leqslant 10^5, M\leqslant 500
对于另外 25\% 的数据, M\leqslant 5000
对于所有数据, 2\leqslant N\leqslant 10^6, 1\leqslant M\leqslant N, 1\leqslant C_i\leqslant M(1\leqslant i\leqslant N) ,在初始状态的绳子上,颜色 1, 2, \ldots, M 都至少出现了一次。