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 | 無額外限制。 |