题解：qoj967 Rectangle Painting

· · 题解

传送门

钦定同一个数不会被插入一个集合两遍（可以用 set 对每个值维护做了操作的连续段）。也就是 x 相同的修改操作区间两两不交。

先考虑离线怎么做。我们把所有操作做完之后倒着撤销。我们把所有操作做完之后维护每个集合的 mex，然后撤销一个区间插入就相当于 \text{mex}\gets \min(\text{mex},x)，可以直接维护。

离线启发我们把 集合 mex 转化为 补集 min。

考虑维护补集，初始时每个集合都是全集，一次操作相当于区间删除，在线段树上每个节点维护 set，即可做到维护区间删除，求区间最大的最小值。

至于保证 x 相同的修改操作区间两两不交这件事，也可以一样的用 set 维护连续段，可能需要线段树维护区间插入，同理。

时间复杂度 \mathcal{O}(q\log^2 n)。