P5101 [JOI 2017 Final] 绳 / Rope

**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T5「[縄](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Rope](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」** 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 \Large\frac{L}{2}$，则将左数第 $i$ 根线 $(2j-L+1\leqslant i\leqslant j)$ 与左数第 $(2j-i+1)$ 根线拧成一股。此时，绳子原本的左端点变为右端点，绳长变为 $j$。 * 两条线的颜色相同才能拧成一股。在将两条线拧成一股前，可以任意改变线的颜色。将线染成其他颜色所需的费用 等于 线的厚度。颜色匹配后，两条线将被拧成一股，新的一股线的厚度 将为 两条线的厚度之和。 我们把绳长缩短至 $2$ 的绳子称为最终的绳子。JOI 希望使得将绳长缩短至 $2$ 所需的费用尽可能小。对于每种颜色，JOI 都想知道，在最终的绳子中包含这种颜色的情况下，将绳长缩短至 $2$ 所需的最小费用。 你的任务是帮 JOI 解决这个问题。

无

无

#### 样例解释 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 通过下述步骤，只需花费 $2$，就可以使得最终的绳子中包含颜色 $1$。 * 折叠绳子使得 原本到左端点的距离为 $2$ 的端点 变为 新的左端点。 * 把左数第 $1$ 根线染成颜色 $1$。折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。注意这次染色的费用为 $2$，因为此时左数第 $1$ 根线的厚度为 $2$。 * 折叠绳子使得 原本到左端点的距离为 $3$ 的端点 变为 新的左端点。 * 折叠绳子使得 原本到左端点的距离为 $1$ 的端点 变为 新的左端点。 #### 数据范围与提示 对于 $15\%$ 的数据，$N\leqslant 15, M\leqslant 10$。 对于另外 $30\%$ 的数据，$N\leqslant 10^5, M\leqslant 10$。 对于另外 $10\%$ 的数据，$N\leqslant 10^5, M\leqslant 500$。 对于另外 $20\%$ 的数据，$N\leqslant 10^5, 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$ 都至少出现了一次。