P11536 [NOISG 2023 Finals] Curtains 题解

根据 CF2163D1 的结论可知，对于一个左端点，只有右端点最大的区间是有用的，因此只需要保留最多 $n$ 个区间。

考虑对询问区间和给定的区间分别排序然后双指针扫描，对于一个询问区间，将右端点在其右端点左侧的覆盖区间加入到线段树中，则此时询问区间 $[ql,qr]$ 合法的充要条件是：

• $[ql,qr]$ 中每个位置都被至少覆盖一层。
• $[ql,qr]$ 中所有位置对应的覆盖左端点的最大值的 $\min$ 值 $=ql$。

发现这个东西就是区间取 $\max$ 区间查询 $\min$，可以简单线段树维护，总时间复杂度为 $O(n\log n)$ 可以通过该题。