set 维护白色区间 · 区间覆盖

用有序集合维护所有「还没被涂黑」的区间。每次涂黑 [L, R] 时,把与它相交的白色区间删掉,再把不相交的残渣插回去。每次输出剩余空位数。

执行覆盖:
未覆盖(白色格子) 已覆盖(黑色格子) set 中的白色区间 当前操作 [L, R] 重叠部分 刚被删除的区间
加载中…
black 0 空位 16 set 大小 1 —

代码(高亮行 = 当前执行)


    

为什么 set 能做这件事?

不变式:set 里存的永远是「还没被涂黑的区间」,它们两两不相交,并且按左端点从小到大排序。

① 快速定位相交区间:lower_bound({L, 0}) 在 O(log n) 内找到第一个左端点 ≥ L 的区间;再看它前一个区间是否与 L 相交。这两步就把所有可能和 [L, R] 相交的区间都圈出来了。

② 一个区间如何被处理:设白色区间为 [l, r],与 [L, R] 相交,重叠部分为 [max(l,L), min(r,R)]。长度累加进 black,然后从 set 中删除它。若 l < newL 说明左边剩一截,插入 [l, newL-1];若 newR < r 说明右边剩一截,插入 [newR+1, r]。

③ 为什么总复杂度是 O(q log q):初始只有 1 个区间。每次操作最多产生 2 个新区间(左右残渣),所以整个过程中出现过的区间总数是 O(q)。每个区间最多被删除一次,因此 while 循环里的删除操作总共执行 O(q) 次,每次 set 操作 O(log q)。

④ 和动态开点线段树的对比:线段树把区间信息存在树节点上,靠懒标记和剪枝控制复杂度;set 则直接把「连续的白色段」作为整体存起来。思路更「离散」,代码更短,同样能做到 O(q log q)。