E-绳_JOI2017-Final比赛真题

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 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\lt L)$ ，使绳子左数第j根线成为绳子的左端点（最左的线），并折叠绳子。也就是说，

如果 $j \leqslant \cfrac{L}{2}$ ，则将左数第i根线 $(1 \leqslant i \leqslant j)$ 与左数第(2j-i+1)根线拧成一股。此时，绳子原本的右端点仍是右端点，绳长变为L-j。
如果 $j\gt \cfrac{L}{2}$ ，则将左数第i根线 $(2j-L+1 \leqslant i \leqslant j)$ 与左数第(2j-i+1)根线拧成一股。此时，绳子原本的左端点变为右端点，绳长变为j。

两条线的颜色相同才能拧成一股。在将两条线拧成一股前，可以任意改变线的颜色。将线染成其他颜色所需的费用等于线的厚度。颜色匹配后，两条线将被拧成一股，新的一股线的厚度将为两条线的厚度之和。

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

输入描述:

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

输出描述:

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

示例1

输入

复制

5 3
1 2 3 3 2

输出

复制

2
1
1

说明

通过下述步骤，只需花费2，就可以使得最终的绳子中包含颜色1。
1.把左数第2根线染成颜色1。折叠绳子使得原本到左端点的距离为1的端点变为新的左端点。现在，从左往右数，线的颜色依次是1,3,3,2，厚度依次是2,1,1,1。
2.把左数第4根线染成颜色1。折叠绳子使得原本到左端点的距离为2的端点变为新的左端点。现在，从左往右数，线的颜色依次是3,1，厚度依次是2,3。
通过下述步骤，只需花费1，就可以使得最终的绳子中包含颜色2和3。
1.折叠绳子使得原本到左端点的距离为3的端点变为新的左端点。现在，从左往右数，线的颜色依次是3,2,1，厚度依次是2,2,1。
2.把左数第3根线染成颜色2。折叠绳子使得原本到左端点的距离为2的端点变为新的左端点。现在，从左往右数，线的颜色依次是2,3，厚度依次是3,2。

示例2

输入

复制

7 3
1 2 2 1 3 3 3

输出

复制

2
2
2

说明

通过下述步骤，只需花费2，就可以使得最终的绳子中包含颜色1。
1.折叠绳子使得原本到左端点的距离为2的端点变为新的左端点。
2.把左数第1根线染成颜色1。折叠绳子使得原本到左端点的距离为1的端点变为新的左端点。注意这次染色的费用为2，因为此时左数第1根线的厚度为2。
3.折叠绳子使得原本到左端点的距离为3的端点变为新的左端点。
4.折叠绳子使得原本到左端点的距离为1的端点变为新的左端点。

示例3

输入

复制

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

输出

复制

3
3
4

备注:

对于的数据，。
对于另外的数据，。
对于另外的数据，。
对于另外的数据，。
对于所有数据，，在初始状态的绳子上，颜色都至少出现了一次。

CC-BY-SA，感谢LOJ分享，译文来自https://loj.ac/problem/2336