← 返回题目列表

AtCoder · joi2017ho_e

E. 绳子

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

配点: 100 点

宝贝 JOI 正在玩绳子。绳子的长度是 N 并从一侧直线延伸到另一侧。绳子很粗 1,长度 1 的字符串 N 它由连接的部分组成。在绳子上 M 使用不同的颜色,从左侧开始: i 字符串的颜色是 C_i (1 \leqq C_i \leqq M)。

JOI君把绳子扭在一起,让它变短。具体而言,根据绳索的长度进行以下操作。 重复直到 2 。

  • 绳子的长度 L 。某个整数 j (1 \leqq j < L) 和从左边开始的长度 将绳子扭在一起,使 j 的位置成为新的左端点。也就是说, 当
    • j \leqq L/2 时,每个 i (1 \leqq i \leqq j) 从左开始 从左起第 i 串 扭动第 2j - i + 1 根绳子。此时,原来为右端点的位置继续为右端点,绳子的长度为 L - j 变为。
    • j > L/2 时,每个 i (2j - L + 1 \leqq i \leqq j) 从左开始 从左起第 i 串 扭动第 2j - i + 1 根绳子。此时,原来为左端点的位置变成了右端点,绳子的长度为 j 变为。
  • 此时,每组绞线的颜色必须相同。琴弦在绞合在一起之前可以重新涂成任何颜色,但重新涂漆的成本与厚度相同。颜色匹配后,将绳子扭在一起,所得绳子的粗细也扭在一起。 2 它是两根弦的粗细之和。

JOI君有一条很长的绳子。 我们希望最大限度地减少 2 之前执行的操作的总成本。 JOI 希望在执行操作时找到所有颜色的最小成本总和,以便最终的绳子包含该颜色。

你的工作就是代表JOI君解决这个问题。

課題

给定构成第一根绳子的绳子的颜色,对于每种颜色,找到包含该颜色且具有长度的绳子。 编写一个程序来找出获得 2 所需的最低成本。


入力

从标准输入读取以下输入。

  • 1 在线 2 整数 给出了 N, M 以空格作为分隔符。这些是构成绳子的绳子。 N 和它们的颜色是 M 表示有不同类型。
  • 2 在线 N 整数 给出了 C_1, C_2, \ldots,C_N 以空格作为分隔符。这些是从左边开始的 i 字符串的颜色是 C_i 。

出力

到标准输出 输出 M 行输出。M 行 c (1 \leqq c \leqq M) 线显示绳索的最终长度。 2 并且绳子有颜色。 c 调整成本总和的最小值以包括 1 行输出。


制限

所有输入数据满足以下条件。

  • 2 \leqq N \leqq 1\,000\,000.
  • 1 \leqq M \leqq N.
  • 1 \leqq C_i \leqq M (1 \leqq i \leqq N).
  • 1 \leqq c \leqq M 的整数 c ,C_i = c 变为 i 存在。

小課題

小課題 1 [15 点]

满足以下条件。

  • N \leqq 15.
  • M \leqq 10.

小課題 2 [30 点]

满足以下条件。

  • N \leqq 100\,000.
  • M \leqq 10.

小課題 3 [10 点]

满足以下条件。

  • N \leqq 100\,000.
  • M \leqq 500.

小課題 4 [25 点]

  • M \leqq 5\,000 很满意。

小課題 5 [20 点]

没有其他限制。


入力例 1

5 3
1 2 3 3 2

出力例 1

2
1
1

使用以下操作 包含的成本 1 包括成本 2 中的长度 可以用 2 来匹配。

  • 从左起 从第 2 为字符串着色 重新绘制为 1 ,长度从左算起 扭转,使 1 的位置成为终点。从左到右,绳子的颜色是 1, 3, 3, 2 厚度为 2, 1, 1, 1 变为。
  • 从左起 从第 4 字符串的颜色 1 ,长度从左算起 扭转,使 2 的位置成为终点。从左到右,绳子的颜色是 3, 1 厚度为 2, 3 变为。

您还可以使用以下操作更改颜色。 2, 3 包括成本 1 中的长度 可以用 2 来匹配。

  • 从左算起的长度 扭转,使 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

使用以下操作 包含的成本 1 包括成本 2 中的长度 可以用 2 来匹配。

  • 从左算起的长度 扭转,使 2 位置成为终点。 扭转,使
  • 从左起 从第 1 字符串的颜色 1 ,长度从左算起 扭转,使 1 的位置为终点。要重新绘制的字符串的粗细 2 因此,成本为 2 请注意,这将会发生。
  • 从左算起的长度 扭转,使 3 位置成为终点。 扭转,使
  • 从左算起的长度 扭转,使 1 位置成为终点。 扭转,使

入力例 3

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

出力例 3

3
3
4

1 在扭转之前,您可以在多个点重新绘制绳子。