AGC040B Two Contests

· · 题解

介绍一个比较直观的想法。

考虑从相互包含的区间入手。
对于区间 a\sube b，如果 b 和 a 分在同一组，则不会影响答案；如果不分在同一组，且另一组此时非空，那么有可能会使答案减小。
所以 a,b 分在同一组不劣，且 b 不会有任何贡献。

我们只留下被包含的区间。那么将这些区间按左端点排序后，右端点也是升序，最优策略一定是分成一段前缀和一段后缀。
证明可以考虑调整法，从前缀和后缀中各选一个数交换，答案一定不会更优。

那么预处理前缀答案和后缀答案即可。

但是注意，我们一开始的结论是基于 “另一组此时非空” 的。所以如果 b 单独成一组，就有可能得到更优的答案。计算每个区间单独成组的答案即可。

时间复杂度 O(n\log n)。

submission.