python/TangDou/AcWing/SegmentTree/P3740_ODT.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

// 用于记录颜色的集合
set<int> colors;

// 柯朵莉树模板
struct Node {
    int l, r;
    mutable int v;
    bool operator<(const Node &b) const {
        return l < b.l;
    }
};
set<Node> s;

// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
    auto it = s.lower_bound({x});
    if (it != s.end() && it->l == x) return it; // 如果x就是一个区间的开头，就不用切割,直接返回这个区间

    it--;
    if (it->r < x) return s.end(); // x太大，超过了最后一个区间的右端点,直接返回s.end()

    int l = it->l, r = it->r, v = it->v;
    s.erase(it);                      // 删掉旧区间
    s.insert({l, x - 1, v});          // 拆分成两个区间
    return s.insert({x, r, v}).first; // 返回新插入区间位置的迭代器
}

void add(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++) it->v += v;
}

void assign(int l, int r, int v) {
    auto R = split(r + 1), L = split(l);
    s.erase(L, R);
    s.insert({l, r, v});
}

// 计算有多少种可见颜色
int countColor(int l, int r) {
    auto R = split(r + 1), L = split(l);
    for (auto it = L; it != R; it++)
        if (it->v) colors.insert(it->v);
    return colors.size();
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);

    int n, m;
    cin >> n >> m;

    // 初始时整个区间颜色id为0
    s.insert({1, n, 0});

    // m个区间统一赋值为i
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        assign(l, r, i); // 给海报区间染色 每个区间颜色不同
    }
    // 输出有几种可见的颜色
    cout << countColor(1, n) << endl;

    return 0;
}