CF2042D 题解

· · 题解

题意

有 n 个用户和 10^9 首歌曲，第 i 个用户喜欢的歌曲是编号在 [l_i,r_i] 的一段连续子区间。

用户 j 称为用户 i 的预测者当且仅当 [l_j,r_j] 包含 [l_i,r_i]。

对于每个用户 i，计算其预测者喜欢的歌曲的并集大小（原题求出结果后需要减去 r_i-l_i+1）。

做法

注意到完全包含的对数可以达到 O(n^2) 级别，逐个计算是不可能的。

考虑对于每个人，如何计算其答案。

考虑简化问题，分别考虑对于一个人，其预测者喜欢的音乐的并集区间的左端点和右端点。

假设当前处理用户 i 的答案。

容易注意到，左端点是在 i 的预测者的左端点里面取最大值，右端点是在 i 的预测者的右端点里面取最小值。

能否二分左右端点呢？

由于左右端点的做法是等价的，此处仅讨论左端点的情况。

此时，二分的目的是求出最大的 l 使得 l 是某个预测者的左端点。

注意到，一个左端点是某个预测者的左端点，当且仅当这个左端点能直接到达的最大右端点大于等于 r_i，当然，这对左端点右端点的组合不能是 (l_i,r_i) 本身。

那么，二分 check 的时候只需要看从 mid 到 l_i 是否存在一个预测者的左端点就可以了，可以 ST 表维护做到 O(1) 判定。