CF786C Till I Collapse

Rick 和 Morty 想要找到 MR. PBH，但他们无法单独完成这件事。因此他们需要 Mr. Meeseeks 的帮助。他们已经生成了 $n$ 个 Mr. Meeseeks，排成一行，编号为 $1$ 到 $n$。每个 Mr. Meeseeks 都有自己的颜色，第 $i$ 个 Mr. Meeseeks 的颜色为 $a_i$。 Rick 和 Morty 正在集结他们的军队，他们想将 Mr. Meeseeks 分成若干个小队。他们不希望小队太花哨，所以每个小队中 Mr. Meeseeks 的颜色种类不超过 $k$ 种。此外，每个小队必须是 Mr. Meeseeks 排队中的一个连续子段。也就是说，对于每个 $1 \leq i \leq e \leq j \leq n$，如果编号为 $i$ 和编号为 $j$ 的 Mr. Meeseeks 在同一个小队里，那么编号为 $e$ 的 Mr. Meeseeks 也必须在那个小队中。 此外，每个小队都需要一个据点，而建造据点是要花钱的，所以他们希望小队的总数尽量少。 Rick 和 Morty 还没有最终确定 $k$ 的具体值，因此他们需要知道对于每个 $k$ 从 $1$ 到 $n$（包括 $1$ 和 $n$），最少需要多少个据点。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示 Mr. Meeseeks 的数量。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示 Mr. Meeseeks 按顺序排列的颜色。

输出一行共 $n$ 个用空格分隔的整数，第 $i$ 个整数表示当 $k$ 取 $i$ 时，最少需要多少个据点。

对于第一个样例测试用例，每种 $k$ 的最优分割方法示例如下： 1. $[1],[3],[4],[3,3]$ 2. $[1],[3,4,3,3]$ 3. $[1,3,4,3,3]$ 4. $[1,3,4,3,3]$ 5. $[1,3,4,3,3]$ 对于第二个样例测试用例，每种 $k$ 的最优分割方法示例如下： 1. $[1],[5],[7],[8],[1],[7],[6],[1]$ 2. $[1,5],[7,8],[1,7],[6,1]$ 3. $[1,5,7],[8],[1,7,6,1]$ 4. $[1,5,7,8],[1,7,6,1]$ 5. $[1,5,7,8,1,7,6,1]$ 6. $[1,5,7,8,1,7,6,1]$ 7. $[1,5,7,8,1,7,6,1]$ 8. $[1,5,7,8,1,7,6,1]$ 由 ChatGPT 5 翻译