自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 23:02:07，当前版本为作者最后更新于2023-07-03 09:43:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

若一个区间的权值 $\ge 4$，取出任意一个对这个值域区间贡献达到 $\max$ 的区间，对着里面的值域分裂成两个区间，显然不比原先劣。所以存在答案使得该答案中每个区间的价值为 $2$ 或 $3$。

并且在给出的区间中，被包含的区间可以直接去掉。所以把剩余的区间按照左端点（或者右端点）排序，维护在某个区间中相邻或相隔一个数的数对。具体来说大概就是用个 set 维护当前区间里面的数，移动到下一个区间的时候就先把要删的删了，然后逐个加入新的数，插进 set 的时候找到增加的对子。

这样只会得到 $O(n)$ 个数对。然后取对数（精度有 $\log n$ 位就够了）dp 即可。

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