本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 01:44:57

题意

有 $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)$ 判定。