离线 + 并查集
* 因为后面的 染色 优先级更大,所以将 染色 操作 存起来,然后 倒序 处理。(离线操作)
* 那么对于后来的染色[L,R], 如果前面的染色已经包含了[L,R],则丢弃,否则要找出[L,R]中未被染色的区间。
* 用并查集 fa[i] 表示 i 位置左边最近未染色的位置是哪里,对于 find(R) < L的 染色 直接丢弃(已经被包含) , 否则 染色 find(R) ,同时令 fa[find(R)] = find(L-1) (表示染色到 L ) , 然后 沿着 find(R)-1走上述过程就行了。
可以证明,每个点只会被染色一次,所以时间复杂度是 O(n)