Rikka with A Long Colour Palette ICPC 2018 Xuzhou R

[ICPC 2018 Xuzhou R] Rikka with A Long Colour Palette

题目链接： [ICPC 2018 Xuzhou R] Rikka with A Long Colour Palette 。

题目描述：

有 $n$ 个线段，第 $i$ 个线段覆盖 $[l_i,r_i)$ 。共 $k$ 种颜色。

你可以为每一个线段分配一个颜色 $c_i$ ，之后对每一个 $i$ ，将区间 $[l_i,r_i)$ 加入颜色 $c_i$ 。

要求使被所有颜色覆盖的面积最大，并构造方案。

$n,k \le 2\times 10^5$ 。

经典按照左端点排序。之后考虑贪心：

• 先将前 $k$ 个线段加入，并赋予颜色 $1\sim k$ 。
• 对于 $i=k+1\sim n$ ，每次肯定要考虑目前右端点最靠前的那个线段并继承她的颜色。
• 正确性是因为她是右端点最靠前的。如果你不继承她的颜色，那么中间的一段必然不可能贡献。

这个贪心思路还是挺顺畅的。

然后求答案考虑扫描线就行。代码不放了。