题解：CF2096F Wonderful Impostors

· · 题解

考虑维护一个数组 ll，其中 ll_r 表示对于右端点 r，最靠左的合法左端点是谁。显然如果区间 [ll_r, r] 范围内的限制可能同时满足，则对于所有 \geq ll_r 的左端点 l，区间 [l, r] 都满足要求。另外，容易发现限制数越多越劣，所以 ll 数组单调不降。因此，我们使用双指针维护，每次 r \to r + 1 时指针不断暴力右移即可预处理 ll 数组，从而 \mathcal{O}(1) 回答每个询问。

为了能够双指针预处理 ll 数组，我们需要一个数据结构 S，支持高效插入和删除两种限制，并能够高效回答目前 S 中的限制们是否能够同时满足。这里我们考虑使用线段树来实现 S。

令 cnt_i 表示原题中「长为 n 的 01 序列」的第 i 个位置被多少全 0 限制覆盖。那么一个至少为 1 的限制 [L, R] 合法当且仅当 \min\limits_{i = L}^R cnt_i = 0。接下来，考虑左端点相同的至少一个 1 的限制。如果短的限制不合法，则无论长的限制怎么样，当前 S 中的限制集合就不合法；如果短的限制合法，那么更长的限制一定也合法，所以只需要考虑右端点最小的那个即可。因此，令 r_a 表示所有左端点为 a 的至少一个 1 的限制中，最小的右端点（如果不存在这样的限制，则令 r_a = +\infty）。

这样，如果存在一个区间 [L, R] 满足 \min\limits_{i = L}^R cnt_i > 0 且 \min\limits_{i = L}^R r_i\le R，则说明存在一个至少为 1 的限制 [a, r_a]，满足 [a,r_a] 完全被一段全 0 限制所覆盖，产生矛盾。我们尝试使用线段树维护这个条件。

考虑判断是否合法的 check() 函数，发现为了实现 check()，我们需要维护所有位置 cnt_i 的最小值 mn，所有位置 r_i 的最小值 minR，以及是否存在一个满足上述「\min\limits_{i = L}^R cnt_i > 0 且 \min\limits_{i = L}^R r_i\le R」条件的区间。当然，为了后续插入操作方便，我们将条件的第一部分改为 \min\limits_{i = L}^R cnt_i > mn。于是我们的 check() 函数可以先判断 minR 和 +\infty 的关系得出是否存在任何至少为 1 的限制，如果不存在直接返回合法；反之一定存在，那么此时如果 mn > 0 则没有任何位置不被限制必须是 0，答案是不合法；最后一定满足 mn = 0，那么 \min\limits_{i = L}^R cnt_i > mn 和 \min\limits_{i = L}^R cnt_i > 0 是等价的，返回线段树上根节点的这个信息即可。

维护节点管辖区间内的 mn 和 minR 是容易的，下面考虑怎么维护 flag（表示是否存在满足上述条件的区间）。容易发现维护 flag 需要在 push up 的时候能够判断跨中点 mid 的那些区间是否满足条件。观察条件，发现 \min\limits_{i = L}^R r_i\le R 这个条件在 [L, R] 向两端伸长的情况下不劣。因此我们再维护一个信息 pre，表示区间中「满足所有 cnt_i > mn 的，最长的前缀的右端点位置」，令 preR 表示这段前缀 pre 所对应的 r_i 的最小值；后缀 suf 与 sufR 同理。在合并过程中，如果某个孩子节点的 mn 与父亲节点的 mn 相同，则可以直接使用 preR 或者 sufR 更新；如果不同，则一定有孩子的 mn 比父亲节点的 mn 大，此时孩子节点中的全部位置满足 cnt_i > mn，因此把孩子节点全部选上即可（贡献恰好为孩子节点的 minR）！

接下来为了维护 preR 和 sufR，只需要再维护整个节点的 r_i 最小值（即 minR）即可，这个过程跟线段是维护最大子段和很像。综上所述，我们对线段树每个区间维护 mn、minR、flag、pre、preR、suf、sufR 即可。

下面考虑插入或删除全 0 限制的情况。容易发现，插入或删除全 0 限制相当于对 cnt 做区间加减 1。由于我们将条件写成 \min\limits_{i = L}^R cnt_i > mn，因此区间加减 cnt_i 不影响上式取值，线段树中除了 mn 其他 6 个信息不会改变！因此直接打个懒标记维护 mn 即可解决全 0 限制的插入与删除操作。

对于插入或删除至少有一个 1 的限制的情况，我们前面说过对于左端点相同者只考虑右端点最小的那个。因此对于叶子节点，我们需要维护插入或删除一个右端点，同时维护右端点最小值，使用 multiset 即可实现。

综上，总时间复杂度为 \mathcal{O}(m \log n + q)。

:::info[参考代码]{open}

提交记录：https://codeforces.com/contest/2096/submission/398101702。

#include<bits/stdc++.h>
#define fo(i, l, r) for(int i = (l); i <= (r); ++i)
using namespace std;
const int N = 200005, inf = 1e9;
int T, n, m, q, x[N], a[N], b[N], ll[N];
multiset<int> s[N];
struct SegT{
    int mn, minR, pre, preR, suf, sufR, tag;
    bool flag;
}t[N << 2];
inline void push_up(int p, int l, int r){
    int mid = (l + r) >> 1;
    t[p].mn = min(t[p << 1].mn, t[p << 1 | 1].mn);
    t[p].minR = min(t[p << 1].minR, t[p << 1 | 1].minR);
    if(t[p << 1].mn == t[p].mn){
        t[p].pre = t[p << 1].pre;
        t[p].preR = t[p << 1].preR;
    }else{
        t[p].pre = max(t[p << 1 | 1].pre, mid);
        t[p].preR = min(t[p << 1].minR, t[p << 1 | 1].preR);
    }
    if(t[p << 1 | 1].mn == t[p].mn){
        t[p].suf = t[p << 1 | 1].suf;
        t[p].sufR = t[p << 1 | 1].sufR;
    }else{
        t[p].suf = min(t[p << 1].suf, mid + 1);
        t[p].sufR = min(t[p << 1 | 1].minR, t[p << 1].sufR);
    }
    int lsuf, lsufR, lflag, rpre, rpreR, rflag;
    if(t[p << 1].mn > t[p].mn){
        lsuf = l;
        lsufR = t[p << 1].minR;
        lflag = (t[p << 1].minR <= mid);
    }else{
        lsuf = t[p << 1].suf;
        lsufR = t[p << 1].sufR;
        lflag = t[p << 1].flag;
    }
    if(t[p << 1 | 1].mn > t[p].mn){
        rpre = r;
        rpreR = t[p << 1 | 1].minR;
        rflag = (t[p << 1 | 1].minR <= r);
    }else{
        rpre = t[p << 1 | 1].pre;
        rpreR = t[p << 1 | 1].preR;
        rflag = t[p << 1 | 1].flag;
    }
    t[p].flag = lflag | rflag;
    if(lsuf <= mid && rpre >= mid + 1 && min(lsufR, rpreR) <= rpre){
        t[p].flag = true;
    }
    return;
}
inline void apply(int p, int k){
    t[p].mn += k, t[p].tag += k;
    return;
}
inline void push_down(int p){
    if(!t[p].tag) return;
    apply(p << 1, t[p].tag), apply(p << 1 | 1, t[p].tag);
    t[p].tag = 0;
    return;
}
inline void build(int p, int l, int r){
    t[p].mn = t[p].tag = t[p].flag = 0;
    if(l == r){
        t[p].minR = t[p].preR = t[p].sufR = inf;
        t[p].pre = -inf, t[p].suf = inf;
        s[l].clear();
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    push_up(p, l, r);
    return;
}
inline void modify1(int p, int l, int r, int ql, int qr, int k){
    if(r < ql || qr < l) return;
    if(ql <= l && r <= qr) return apply(p, k), void();
    int mid = (l + r) >> 1;
    push_down(p);
    modify1(p << 1, l, mid, ql, qr, k), modify1(p << 1 | 1, mid + 1, r, ql, qr, k);
    push_up(p, l, r);
    return;
}
inline void modify2(int p, int l, int r, int x, int k, int o){
    if(x < l || x > r) return;
    if(l == r){
        if(o == 1){
            s[x].insert(k);
            t[p].minR = *s[x].begin();
        }else{
            s[x].erase(s[x].find(k));
            if(s[x].empty()){
                t[p].minR = inf;
            }else t[p].minR = *s[x].begin();
        }
        return;
    }
    int mid = (l + r) >> 1;
    push_down(p);
    modify2(p << 1, l, mid, x, k, o), modify2(p << 1 | 1, mid + 1, r, x, k, o);
    push_up(p, l, r);
    return;
}
inline void insert(int x, int a, int b){
    if(!x){
        modify1(1, 1, n, a, b, 1);
        return;
    }
    modify2(1, 1, n, a, b, 1);
    return;
}
inline void erase(int x, int a, int b){
    if(!x){
        modify1(1, 1, n, a, b, -1);
        return;
    }
    modify2(1, 1, n, a, b, -1);
    return;
}
inline bool check(){
    if(t[1].minR == inf) return true;
    if(t[1].mn > 0) return false;
    return !t[1].flag;
}
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T; while(T--){
        cin >> n >> m;
        ll[0] = 1;
        build(1, 1, n);
        fo(i, 1, m){
            cin >> x[i] >> a[i] >> b[i];
            insert(x[i], a[i], b[i]);
            ll[i] = ll[i - 1];
            while(ll[i] < i && !check()){
                erase(x[ll[i]], a[ll[i]], b[ll[i]]);
                ll[i]++;
            }
        }
        cin >> q; while(q--){
            int l, r; cin >> l >> r;
            cout << (l >= ll[r] ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

:::