题解

思路

固定 $k$ 后，从当前尚未覆盖的最左位置开始，把这一段尽量向右延伸，直到再加入下一个位置就会出现第 $k+1$ 种颜色。随后从这个新位置开始下一段。

这个贪心是最优的。第一段的右端点越靠右，留给后续段的后缀只会越短，不会让剩余部分需要更多之外的额外代价。因此任意最优方案的第一段都可以替换成最长合法前缀而不增加段数；对剩余后缀重复这一论证即可。

做法

各子任务

当 $n$ 很小时，可以枚举相邻位置之间是否切分。对每一种完整划分统计每段颜色数，并更新所有可容纳该划分的 $k$。

当所有颜色两两不同时，每一段最多容纳 $k$ 个位置，答案直接为 $\lceil n/k\rceil$。

设全序列共有 $D$ 种颜色。当 $D\le 20$ 时，只需对 $k=1,2,\ldots,D-1$ 逐次线性执行贪心；对 $k\ge D$，整个序列本身就是一段。复杂度为 $O(nD)$。

当 $n\le 2000$ 时，对每个 $k$ 都用双指针或计数数组线性执行一次贪心，总复杂度为 $O(n^2)$。

满分做法

对每个起点 $l$，考虑后缀 $a_l,a_{l+1},\ldots,a_n$。只保留每种颜色在这个后缀中的第一次出现位置，并在这些位置上标记 $1$。若这些标记从左到右的第 $k+1$ 个位置为 $p$，那么从 $l$ 开始的最长合法段恰好是 $[l,p-1]$，下一段应从 $p$ 开始；若不足 $k+1$ 个标记，则当前段可以直接覆盖到序列末尾。

从 $l+1$ 的后缀转到 $l$ 的后缀时，只发生两处变化：位置 $l$ 变为当前颜色的第一次出现，而该颜色原先的第一次出现位置（如果存在）不再被标记。因此可以从右向左建立一组持久化线段树，每个版本表示相应后缀的首现位置集合。

固定 $k$ 后，从位置 $1$ 开始，不断在当前版本中查询第 $k+1$ 个标记并跳到该位置，跳跃次数就是答案。除最后一段外，每一段至少包含 $k$ 个位置，所以固定 $k$ 的跳跃次数为 $O(n/k+1)$。所有 $k$ 的跳跃次数之和为 $O(n\log n)$，每次在线段树上查询需要 $O(\log n)$，故总时间复杂度为 $O(n\log^2 n)$。

复杂度

建立所有持久化版本需要 $O(n\log n)$ 的时间和空间；求全部答案额外使用 $O(n\log^2 n)$ 时间。因此总时间复杂度为 $O(n\log^2 n)$，空间复杂度为 $O(n\log n)$。