题解：CF2096F Wonderful Impostors

· · 题解

0. 题外话

非常好的题目，使我的线段树旋转。

1. 形式化题意

有一个长度为 n 的 01 序列 A。

给出 m 个命题，其中第 i 个命题形如：

你需要回答 q 次询问，每次询问形如：

可离线。

数据范围：1 \le n, m, q \le 2 \cdot 10^5。

2. 题目讲解

不妨先考虑暴力。

考虑对于每次询问，尝试写出一个可行的 A。

观察到，对于一个命题 i：

显然 x_i=0 的命题限制更加严格，其直接要求：对于每个 \displaystyle k \in \bigcup_{i \in [l, r], x_i=0} [a_i, b_i]，有 A_k=0。

我们令上述 A_k=0。

接下来，考虑让 A 满足 x_i=1 的条件。

注意到：对于一个未确定的位置 k，A_k=1 总是不劣于 A_k=0。

因此令其余 A_k=1。

接下来，依次检查所有 x_i=1 的命题即可。

时间复杂度：O(nmq)。

注意到：对于上述算法，实际需要进行的操作有：

显然上述操作可以使用 01 线段树维护。

更具体来讲：

对于每次询问，建立一棵大小为 n 的初值为 1 的 01 线段树 A。

枚举每个 x_i=0 的命题，对于每个命题 i，将区间 [a_i, b_i] 赋值为 0。

随后，枚举每个 x_i=1 的命题 i，检查 \displaystyle \bigvee_{k=a_i}^{b_i} A_k = 1 是否成立。

时间复杂度：O(mq \log n)。

由于每个命题都是在给 A 添加更多限制，因此，若存在一个 A 使得 [l, r] 中的全部命题成立，则该 A 一定也可以使得任意一个 [l, r] 的子区间中的全部命题成立。

故考虑使用尺取法预处理：对于每个 l，满足存在一个 A 使得 [l, r] 中的全部命题成立的最大的 r。

然而，当前做法中，01 线段树无法移除某次赋值带来的影响。

考虑使用经典做法：将 01 线段树转化为普通线段树。

建立一棵大小为 n 的初值为 0 的线段树 c。

每次加入一个 x_i=0 的命题 i 时，将 [a_i, b_i] 的值加 1。

类似地，每次移除一个 x_i=0 的命题 i 时，将 [a_i, b_i] 的值减 1。

注意到：A_k=1 当且仅当 c_k=0。

因此，每次加入新命题时，只需枚举 [l, r] 中每个 x_i=1 的命题，检查 \displaystyle \min_{k=a_i}^{b_i} c_k = 0 是否成立。

时间复杂度：O(m^2 \log n + q)。

当新加入的命题满足 x_i=1 时，只需检查新加入的命题即可，因此瓶颈在于：当新加入的命题满足 x_i=0 时，需要枚举 [l, r] 中每个 x_i=1 的命题并检查是否成立。

考虑不成立时的情况，即：加入命题 i \ (x_i=0) 后，命题 j \ (x_j=1) 不成立。

显然，此时有：加入命题 i 后，对于每个 k \in [a_j, b_j]，有 c_k>0。

同时，尺取法隐含着一个条件：若算法可以运行到尝试加入命题 i，则说明截至加入命题 i 前，命题 j 成立，故 [a_i, b_i] \cap [a_j, b_j] \ne \varnothing，否则命题 i 对 A 的修改不会让命题 j 不成立。

由于：

故加入命题 i 后，[a_i, b_i] 与 [a_j, b_j] 位于同一个极长非 0 串中。

回到原问题，则原问题转化为：找出加入命题 i 后 [a_i, b_i] 所在的极长非 0 串，记该串为 [x, y]，检查 [l, r] 中是否存在 x_j=1 的命题 j，满足 [a_j, b_j] \subseteq [x, y]，即 x \le a_j \le b_j \le y。

找出极长非 0 串是简单的，由于 \displaystyle x = (\max_{k \in [1, a_i), c_k=0} k) + 1，\displaystyle y = (\min_{k \in (b_i, n], c_k=0} k) - 1，只需查找 \displaystyle \max_{k \in [1, a_i), c_k=0} k 和 \displaystyle \min_{k \in (b_i, n], c_k=0} k 即可。实现上，可采取线段树维护区间最小值与最小/大最小值点的方法。

故难点在于：检查 [l, r] 中是否存在 x_j=1 的命题 j，满足 x \le a_j \le b_j \le y。

注意到，该问题可转化为：是否存在满足 (j \in [l, r]) \wedge (x_j=1) \wedge (b_j \in [x, y]) 的 j，使得 a_j \ge x。

其又可进一步转化为：检查 \displaystyle \max_{j \in [l, r], x_j=1, b_j \in [x, y]} a_j \ge x 是否成立。

考虑求出 \displaystyle \max_{j \in [l, r], x_j=1, b_j \in [x, y]} a_j。

注意到：\displaystyle \max_{j \in [l, r], x_j=1, b_j \in [x, y]} a_j = \max_{k=x}^y \max_{j \in [l, r], x_j=1, b_j=k} a_j。

令 \displaystyle d_k := \max_{j \in [l, r], x_j=1, b_j=k} a_j。

对于每个 k，维护 d_k 是简单的，只需为每个 k 建立一个 multiset 并维护加入和移除即可，故只需求出 \displaystyle \max_{k=x}^y d_k。

这显然是好计算的，由于每次加入或移除 x_j=1 的命题 j 至多只会改变 1 个 d_k，直接使用线段树维护即可。

时间复杂度：O(m \log n + q)。

:::success[AC Code]

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

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <numeric>
#include <random>
#include <vector>
#include <set>
typedef unsigned int uint;
typedef long long longlong;
typedef unsigned long long ulonglong;
typedef long double longdouble;
#define double longdouble
#define int longlong
#define uint ulonglong
#define y0 a67676767
#define y1 b67676767
#define fil(a, x) fill(a, a + (sizeof a) / (sizeof a[0]), x)
#define fil2(a, x) fill(a[0], a[0] + (sizeof a) / (sizeof a[0][0]), x)
using namespace std;

const int N = 2e5 + 5;

// 区间加 / 区间求 min / 区间 first/last index of min
struct node1{
    int l, r, ls, rs, lz, mn, lf, rt;
    inline int len(){ return r - l + 1; }

    inline void set(int x){
        mn = x, lf = rt = l;
    }

    inline void modify(int x){
        lz += x, mn += x;
    }

    inline void merge(node1 a, node1 b){
        if (a.mn < b.mn){
            mn = a.mn, lf = a.lf, rt = a.rt;
        }
        else if (a.mn == b.mn){
            mn = a.mn, lf = a.lf, rt = b.rt;
        }
        else{
            mn = b.mn, lf = b.lf, rt = b.rt;
        }
    }

    node1(){
        l = ls = rs = lz = lf = rt = 0, r = -1, mn = 9e18;
    }
};

// 区间加 / 区间求 max
struct node2{
    int l, r, ls, rs, lz, mx;
    inline int len(){ return r - l + 1; }

    inline void set(int x){
        mx = x;
    }

    inline void modify(int x){
        lz = x, mx = x;
    }

    inline void merge(node2 a, node2 b){
        mx = max(a.mx, b.mx);
    }

    node2(){
        l = ls = rs = lz = mx = 0, r = -1;
    }
};

// 线段树模板
const int S = N << 1;

template<typename T>
struct smt{
    int cnt; T a[S];

    inline int nnode(int l, int r){
        a[++cnt] = T();
        a[cnt].l = l, a[cnt].r = r;
        return cnt;
    }

    inline void build(int x){
        int l = a[x].l, r = a[x].r;
        if (l == r){
            a[x].set(0);
            return;
        }
        int mid = (l + r) >> 1;
        build(a[x].ls = nnode(l, mid));
        build(a[x].rs = nnode(mid + 1, r));
        a[x].merge(a[a[x].ls], a[a[x].rs]);
    }

    inline int init(int n){
        cnt = 0;
        int rt = nnode(1, n);
        build(rt);
        return rt;
    }

    inline void update(int x){
        if (a[x].lz){
            a[a[x].ls].modify(a[x].lz), a[a[x].rs].modify(a[x].lz);
            a[x].lz = 0;
        }
    }

    inline void modify(int x, int s, int t, int d){
        if (a[x].r < s || t < a[x].l){
            return;
        }
        if (s <= a[x].l && a[x].r <= t){
            a[x].modify(d);
            return;
        }
        update(x);
        modify(a[x].ls, s, t, d), modify(a[x].rs, s, t, d);
        a[x].merge(a[a[x].ls], a[a[x].rs]);
    }

    inline T query(int x, int s, int t){
        if (a[x].r < s || t < a[x].l){
            return T();
        }
        if (s <= a[x].l && a[x].r <= t){
            return a[x];
        }
        update(x);
        T tmp; tmp.merge(query(a[x].ls, s, t), query(a[x].rs, s, t));
        return tmp;
    }
}; smt<node1> smt1; smt<node2> smt2;

// 主函数
int n, m, q;
int a[N], b[N], ans[N];
bool ty[N];
multiset<int> s[N];

// 加入 0
inline bool add0(int a, int b){
    smt1.modify(1, a, b, 1);
    node1 t1 = smt1.query(1, 1, a), t2 = smt1.query(1, b, n);
    int x = t1.mn ? 1 : t1.rt + 1, y = t2.mn ? n : t2.lf - 1;
    if (smt2.query(1, x, y).mx < x){
        return 1;
    }
    smt1.modify(1, a, b, -1);
    return 0;
}

// 加入 1
inline bool add1(int a, int b){
    int t = smt1.query(1, a, b).mn;
    if (smt1.query(1, a, b).mn){
        return 0;
    }
    s[b].insert(a);
    smt2.modify(1, b, b, *prev(s[b].end()));
    return 1;
}

inline bool add(int x){
    return ty[x] ? add1(a[x], b[x]) : add0(a[x], b[x]);
}

// 移除 0
inline void del0(int a, int b){
    smt1.modify(1, a, b, -1);
}

// 移除 1
inline void del1(int a, int b){
    s[b].erase(s[b].lower_bound(a));
    smt2.modify(1, b, b, s[b].empty() ? 0 : *prev(s[b].end()));
}

inline void del(int x){
    ty[x] ? del1(a[x], b[x]) : del0(a[x], b[x]);
}

inline void solve(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> ty[i] >> a[i] >> b[i];
    }
    smt1.init(n); smt2.init(n);
    for (int i = 1; i <= n; i++){
        s[i].clear();
    }
    for (int l = 1, r = 0; l <= m; l++){
        while (r < m && add(r + 1)){
            r++;
        }
        ans[l] = r;
        del(l);
    }
    cin >> q;
    while (q--){
        int l, r; cin >> l >> r;
        cout << (r <= ans[l] ? "YES\n" : "NO\n");
    }
}

signed main(){
    // freopen("ceshi.in", "r", stdin);
    // freopen("ceshi.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    // cout << setfill('0');
    // cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T--){
        solve();
    }
    return 0;
}

:::