|
|
#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;
|
|
|
} |
