区间覆盖询问题解

思路推导

直接保存 $N$ 个格子的颜色不可行，因为 $N$ 可达 $10^9$。真正发生变化的只有区间端点，因此维护当前仍为白色的若干极大连续区间。

这些白色区间两两不交，并按左端点有序。一次染色只会影响与 $[L,R]$ 相交的白色区间：相交部分被删除，最多留下位于 $L$ 左侧和 $R$ 右侧的两个白色区间。

做法

初始在有序集合中放入白色区间 $[1,N]$，并令 white=N。

处理 $[L,R]$ 时，先找到左端点不大于 $L$ 的最后一个白色区间，检查它是否与操作区间相交；随后按左端点从小到大处理所有左端点不超过 $R$ 的白色区间。对于每个相交区间，先从集合和白色总数中删除整个区间，再把位于 $[L,R]$ 外的左、右残段重新加入。最后输出 white。

正确性证明

初始集合只含 $[1,N]$，恰好表示全部白色格子。

假设一次操作前，集合中的区间恰好是不相交的极大白色区间。与 $[L,R]$ 不相交的区间不会改变；算法不修改它们。每个相交区间中，交集部分按题意变黑，而算法仅保留交集左侧和右侧仍为白色的部分。这些残段与其他白色区间仍不相交，并且它们的并集恰好是操作后的全部白色格子。

算法同步减去被删除区间长度并加回残段长度，因此维护的白色总数也始终正确。由归纳法，每次输出均正确。

复杂度分析

每个白色区间被删除后至多产生两个新区间。一次操作除有序集合查找外，只处理实际被删除的区间；全程区间插入和删除次数为 $O(Q)$。总时间复杂度为 $O(Q\log Q)$，空间复杂度为 $O(Q)$。