P15244 [NHSPC 2025] 彩色游行

缤纷的游行活动，聚集了大量的人潮，大家穿着鲜艳的服装，排队一个一个往前移动。整个队伍共有 $n$ 个人，其中从头数来第 $i$ 个人的服装上有出现编号为 $l_i, l_i + 1, \dots, r_i$ 的颜色。 为了让活动更有特色，游行的总指挥决定把参加游行队伍分成若干个小队，其中每个小队为原本队伍的连续片段，而每个人都属于恰一个小队。每个小队的得分为队中成员服装的**多样性**，也就是有出现在至少一个队员服装上的颜色编号的种类数。整个队伍的总分即为各个小队的得分加总。 总指挥尚未确定该将整个队伍分成几个小队，他想知道对于所有 $x = 1, 2, \dots,k$，若将队伍分成恰 $x$ 个小队，队伍的总分最大可以是多少？请写一支程序帮助总指挥。

$$ \begin{aligned} &n \; k \\ &l_1 \; r_1 \\ &l_2 \; r_2 \\ &\vdots \\ &l_n \; r_n \end{aligned} $$ - $n$ 为整个队伍的人数。 - $k$ 为总指挥希望的小队数量上限。 - $l_i, r_i$ 代表第 $i$ 个人服装上出现的颜色编号为 $l_i, l_i + 1, \dots, r_i$。

$$ \begin{aligned} &ans_1 \; ans_2 \; \cdots \; ans_k \end{aligned} $$ - $ans_x$ 代表分成恰 $x$ 个小队的总分最大值。

### 数据限制 * $1 \le n\le 10^5$。 * $1 \le k\le \min(n, 20)$。 * $1 \le l_i \le r_i \le 10^9$。 * 输入的数皆为整数。 ### 评分说明 本题共有四组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分數 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 6 | $k = 1$。 | | 2 | 15 | $n \le 500$。 | | 3 | 41 | $1 \le l_i = r_i \le 10^5$。 | | 4 | 38 | 无额外限制。 |