CF2096F Wonderful Impostors

题解

看到题意很容易想到用双指针来维护所有可行的区间，但是显然不能对所有的 1 区间来维护所有的可行区间，这样的区间数量会太多，我们无法快速进行判断。

所以只能对满足答案的所有区间进行双指针，这就要求我们如何快速插入和删除区间 0​ 区间和 1​ 区间。

我们维护一棵线段树表示节点 i 被 0 区间覆盖的次数，那么插入 1 区间的时候只用访问区间 min是否为 0 即可，插入 0 区间直接区间加。

需要注意的是，插入 0 区间的时候，可能会导致原来可行的 1 区间变得不可行。

我们不妨考虑它会让什么样的区间不可行？我们只需要对于左端点 $a_l$ 找到一个向左的最长非零覆盖段 $[c_l,a_l)$ 和右端点 $a_r$ 找到一个向右的最长非零覆盖段 $(a_r,c_r]$ （线段树上二分）。那么被 $[c_l,c_r]$ 覆盖的所有 $1$ 区间都会变得不可行，只需要用线段树来维护每个以节点 i 为 1 区间右端点的左端点最大值，相当于判断前缀 max 是否 $\ge c_l$ 。

删除操作怎么办？

加入一个区间后，如果使答案变得错误，我们需要将左端点对应的区间弹出，但是好像很难判断弹出之后的区间集合是否正确。

考虑我们在进行双指针的时候，一直保持当前区间集合的正确性，也就是说，我们可以尝试插入右端点，如果插入错误，我们马上将右端点带来的影响消除，然后删除左端点，直到可以成功插入右端点为止，那么在这个过程中就可以对于每一个右端点求出了一个最小的左端点，依此来判断答案即可。

自然的，由于保证了区间集合的正确性，那么我们删除左端点的时候只需要做逆操作就可以了，注意第二棵线段树的每个叶子节点需要用 set 来维护最大值。

时间复杂度 $O(n\log n)$