python/TangDou/AcWing/SegmentTree/P3740_1.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
// 无法AC
const int N = 1e5 + 7;

struct Node {
    int l, r;
    int color; // 哪种颜色的海报
    int tag;   // 表示这个区间的数被修改了为同一个数
} tr[N << 4];

int T, n;
int l[N], r[N];
int vis[N], ans;

int b[N], bl; // 离散化数组

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    tr[u].color = 0;
    tr[u].tag = -1;

    if (l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void pushup(int u) {
    if (tr[u].tag) {
        tr[u << 1].color = tr[u].color;
        tr[u << 1 | 1].color = tr[u].color;
        tr[u << 1].tag = tr[u << 1 | 1].tag = 1;
        tr[u].tag = 0;
    }
}

void modify(int u, int l, int r, int x) {
    if (l <= tr[u].l && r >= tr[u].r) {
        tr[u].color = x;
        tr[u].tag = 1;
        return;
    }
    pushup(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid) modify(u << 1, l, r, x);
    if (r > mid) modify(u << 1 | 1, l, r, x);
}

void query(int u, int l, int r) {
    if (tr[u].tag == -1) return;

    if (tr[u].tag) {
        if (!vis[tr[u].color] && tr[u].color) {
            ++ans;
            vis[tr[u].color] = 1;
        }
        return;
    }
    int mid = (l + r) >> 1;
    query(u << 1, l, r);
    query(u << 1 | 1, l, r);
}
/*
答案：
4
*/
int main() {
#ifndef ONLINE_JUDGE
    freopen("P3740.in", "r", stdin);
#endif
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        ans = 0;
        memset(vis, 0, sizeof vis);
        memset(tr, 0, sizeof tr);
        bl = 0;
        for (int i = 1; i <= n; i++) {
            cin >> l[i] >> r[i];
            b[++bl] = l[i];
            b[++bl] = r[i];
            b[++bl] = r[i] + 1; // 区间覆盖问题，为防止缝隙问题，需要r+1也入离散化数组
        }
        sort(b + 1, b + 1 + bl);
        int tot = unique(b + 1, b + 1 + bl) - b - 1;

        build(1, 1, tot);

        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            l[i] = lower_bound(b + 1, b + 1 + bl, l[i]) - b;
            r[i] = lower_bound(b + 1, b + 1 + bl, r[i]) - b;
            modify(1, l[i], r[i], ++cnt);
        }
        query(1, 1, tot);
        printf("%d\n", ans);
    }
    return 0;
}