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