题解：CF2096F Wonderful Impostors

设 $f_r$ 表示最小的左端点 $l$，使得 $[l,r]$ 区间的询问均可合法。在处理询问时，转化为判断是否 $f_r \le l$ 合法即可。

首先考虑如何求出 $f_i$。尝试使用双指针，当前 $[l,r]$ 区间的询问均合法，当加入 $r’=r + 1$ 后，若区间不合法，则进行 $l’ = l + 1$ 操作直到 $[l’,r’]$ 合法。

那么现在的难点便是如何检验区间的合法性。

定义标记数组 $\{v_1,v_2,\cdots,v_n\}$，初始均为 $0$。当 $x_i = 0$ 时，进行区间加 $1$ 操作。当 $x_i = 1$ 时，若某一时刻 $\min\{v_{a_i},v_{a_{i + 1}},\cdots,v_{b_i}\} > 0$，则说明该时刻的情况不合法。当 $x_i = 1$ 时，我们可以直接通过线段树维护区间最小值来判断合法性。但是最棘手的部分是当加入 $x_i = 0$ 的操作时，会影响到之前 $x_i = 1$ 的部分。

令 $p_i$ 表示所有 $x_j = 1$ 且 $b_j = p_i$ 的操作所对应的 $a_j$ 的最大值，即 $p_i = \max\limits_{x_j = 1,b_j = i} \{a_j\}$。当增加一个 $x_i = 0$ 的操作时，设 $[x,y]$ 表示在加入 $[a_i,b_i]$ 区间后，满足 $\min\{v_{x},v_{a_{i + 1}},\cdots,v_{y}\} > 0$ 且 $[a_i,b_i] \subseteq [x,y]$ 的最大区间，若 $\max \{p_x,p_{x + 1},\cdots,p_y\} < x$，即可说明该操作的合法性。考虑维护 $p_i$，线段树维护最大值即可。当然，由于涉及 $a_i$ 的删减，用 multiset 处理单点，后上传到线段树上即可实现。

最后考虑如何快速求出加入 $[a_i,b_i]$ 后的扩展区间 $[x,y]$。线段树与二分的结合显然可以实现，但是总时间复杂度为 $O(n \log^2 n)$，亲测会超时，故考虑线段树二分。注意，应该找到 $a_i$ 从左往右数第一个 $v_i$ 为 $0$，$b_i$ 右侧第一个为 $v_i$ 为 $0$ 的位置。

因此，最后的时间复杂度为 $O(n \log n)$。

#include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define pii pair <int,int>
using namespace std;
const int MAX = 2e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
struct node
{
    int ty,l,r;
} a[MAX];
int t,n,m,q,f[MAX];
multiset <int> s[MAX];
class seg1
{
    int n;vector <int> tree,tmp;
    void pushdown (int cur)
    {
        if (!tmp[cur]) return ;
        tree[cur << 1] += tmp[cur];tree[cur << 1 | 1] += tmp[cur];
        tmp[cur << 1] += tmp[cur];tmp[cur << 1 | 1] += tmp[cur];
        tmp[cur] = 0;
    }
    void pushup (int cur) {tree[cur] = min (tree[cur << 1],tree[cur << 1 | 1]);}
    public : 
    seg1 (int n) : n (n),tree (4 * n + 1,0),tmp (4 * n + 1,0) {}
    void modify (int cur,int l,int r,int x,int y,int v)
    {
        if (x <= l && y >= r)
        {
            tree[cur] += v;tmp[cur] += v;
            return ;
        }
        int mid = (l + r) >> 1;
        pushdown (cur);
        if (x <= mid) modify (cur << 1,l,mid,x,y,v);
        if (y > mid) modify (cur << 1 | 1,mid + 1,r,x,y,v);
        pushup (cur);
    }
    int query (int cur,int l,int r,int x,int y)
    {
        if (x <= l && y >= r) return tree[cur];
        int mid = (l + r) >> 1,res = INF;
        pushdown (cur);
        if (x <= mid) res = min (res,query (cur << 1,l,mid,x,y));
        if (y > mid) res = min (res,query (cur << 1 | 1,mid + 1,r,x,y));
        return res;
    }
    int search_L (int cur,int l,int r,int x,int y)
    {
        if (l == r) return !tree[cur] ? l : n + 1;
        pushdown (cur);
        if (x <= l && y >= r)
        {
            int mid = (l + r) >> 1;
            if (!tree[cur << 1]) return search_L (cur << 1,l,mid,x,y);
            else return search_L (cur << 1 | 1,mid + 1,r,x,y);
        }
        else
        {
            int mid = (l + r) >> 1,res = n + 1;
            if (x <= mid) res = search_L (cur << 1,l,mid,x,y);
            if (res == n + 1 && y > mid) res = search_L (cur << 1 | 1,mid + 1,r,x,y);
            return res;
        }
    }
    int search_R (int cur,int l,int r,int x,int y)
    { 
        if (l == r) return !tree[cur] ? l : 0;
        pushdown (cur);
        if (x <= l && y >= r)
        {
            int mid = (l + r) >> 1;
            if (!tree[cur << 1 | 1]) return search_R (cur << 1 | 1,mid + 1,r,x,y);
            else return search_R (cur << 1,l,mid,x,y);
        }
        else
        {
            int mid = (l + r) >> 1,res = 0;   
            
            if (y > mid) res = search_R (cur << 1 | 1,mid + 1,r,x,y);
            if (!res && x <= mid) res = search_R (cur << 1,l,mid,x,y);
            return res;
        }
    }
};
class seg2
{
    int n;vector <int> tree;
    void pushup (int cur) {tree[cur] = max (tree[cur << 1],tree[cur << 1 | 1]);}
    public :
    seg2 (int n) : n (n),tree (4 * n + 1,0) {for (int i = 1;i <= n;++i) s[i].clear ();}
    void modify (int cur,int l,int r,int x,int v,int ty)
    {
        if (l == r)
        {
            if (!ty) s[l].insert (v);
            else s[l].erase (s[l].find (v));
            if (!s[l].empty ()) tree[cur] = *(--s[l].end ());
            else tree[cur] = 0;
            return ;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) modify (cur << 1,l,mid,x,v,ty);
        else modify (cur << 1 | 1,mid + 1,r,x,v,ty);
        pushup (cur);
    }
    int query (int cur,int l,int r,int x,int y)
    {
        if (x <= l && y >= r) return tree[cur];
        int mid = (l + r) >> 1,res = 0;
        if (x <= mid) res = max (res,query (cur << 1,l,mid,x,y));
        if (y > mid) res = max (res,query (cur << 1 | 1,mid + 1,r,x,y));
        return res;
    }
};
int main ()
{
    t = read ();
    while (t--)
    {
        n = read ();m = read ();
        seg1 tr1 (n + 1);seg2 tr2 (n + 1);
        for (int i = 1;i <= m;++i) a[i].ty = read (),a[i].l = read (),a[i].r = read ();
        int l = 1,r = 0;
        while (r < m)
        {
            ++r;
            if (!a[r].ty) tr1.modify (1,1,n,a[r].l,a[r].r,1);
            else tr2.modify (1,1,n,a[r].r,a[r].l,0);
            while (l <= r) 
            {
                if (!a[r].ty)
                {
                    int dl = tr1.search_R (1,1,n,1,a[r].l) + 1,dr = tr1.search_L (1,1,n,a[r].r,n) - 1;
                    if (tr2.query (1,1,n,dl,dr) < dl) break;
                }
                else if (!tr1.query (1,1,n,a[r].l,a[r].r)) break;
                if (!a[l].ty) tr1.modify (1,1,n,a[l].l,a[l].r,-1);
                else tr2.modify (1,1,n,a[l].r,a[l].l,1);
                ++l;
            }
            f[r] = l;
        }
        q = read ();
        while (q--)
        {
            int l = read (),r = read ();
            puts (f[r] <= l ? "YES" : "NO");
        }
    }
    return 0;
}
inline int read ()
{
    int s = 0;int f = 1;
    char ch = getchar ();
    while ((ch < '0' || ch > '9') && ch != EOF)
    {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar ();
    }
    return s * f;
}