题解 莫队的 1.5 近似构造

critnos · 2023-07-03 09:43:30 · 题解

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

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

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

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