问题描述
你需要维护一个数据结构,支持:加入/删除一个区间,加入/删除一个点,查询是否存在区间到点的完美匹配,使每个区间都在匹配中。保证任何时候不存在两个互相包含的区间。
题解
考虑 Hall 定理,发现如果选出若干个区间,那么我们只关心这些区间的并。进一步可以发现只用考虑这个并是一个连续区间的情况。设这个并为 ([L,R])。由 Hall 定理,我们只需要任意一个 ([L,R]) 包含的区间个数 (le) ([L,R]) 的点个数。
那么如果存在一个区间 ([l,r]supseteq [L,R]),那么 ([L,R]) 必然不包含任何区间,此时显然成立。
否则,记 (s_i) 为前缀点的数量,(a_i) 为右端点 (le i) 的区间数量,(b_i) 为左端点 (le i) 的区间数量,分讨发现包含于 ([L,R]) 的区间数量即为 (a_R-b_{L-1})(用到 ([L,R]) 不包含于任何区间的性质!),则合法当且仅当对于所有 (Lle R) 有 ((s_R-s_{L-1})-(a_R-b_{L-1})ge 0),即 ((b_{L-1}-s_{L-1})+(s_R-a_R)ge 0)。
于是在每个线段树节点上分别维护 (b_i-s_i) 和 (s_i-a_i) 的最大值,只需支持区间加,求最大值即可,合并左右儿子节点是容易的。时间复杂度 (O(nlog n))。