LeoPace @ 2022-06-15 17:01:36
#include<bits/stdc++.h>
using namespace std;
struct node{
int l, r, color=-1;
};
struct poster{
int l, r;
};
vector<poster> po;
vector<node> tree;
vector<int> a;
set<int> temp;
set<int>::iterator it;
vector<bool> colorVis;
int ans;
inline int getmid(int l, int r) {return l + (r-l)/2;}
void pushdown(int k){
if(tree[k].l == tree[k].r) return;
if(tree[k].color==-1) return;
tree[k*2].color = tree[k].color;
tree[k*2+1].color = tree[k].color;
tree[k].color = -1;
}
void build(int k, int l, int r){
tree[k].l = l, tree[k].r = r;
if(tree[k].l == tree[k].r) return;
int mid = getmid(l, r);
build(k*2, l, mid);
build(k*2+1, mid+1, r);
}
void dye(int k, int l, int r, int c){
if(tree[k].color != -1) pushdown(k);
if(tree[k].l >= l && tree[k].r <= r){
tree[k].color = c;
return;
}
if(tree[k].color != -1)pushdown(k);
int mid = getmid(tree[k].l, tree[k].r);
if(mid >= l) dye(k*2, l, mid, c);
if(mid < r) dye(k*2+1, mid+1, r, c);
}
void query(int k, int l, int r){
if(tree[k].color != -1) pushdown(k);
if(tree[k].l == tree[k].r){
if(tree[k].color != -1) pushdown(k);
if(tree[k].color != -1&&!colorVis[tree[k].color]){
ans++;
colorVis[tree[k].color] = true;
}
return;
}
if(tree[k].color != -1) pushdown(k);
int mid = getmid(tree[k].l, tree[k].r);
query(k*2, l, mid);
query(k*2+1, mid+1, r);
}
int main(void){
int n, m, co = 1;
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
scanf("%d%d", &n, &m);
colorVis.resize(m+1);
a.push_back(0);
po.resize(m+1);
for(int i = 1; i <= m; i++){
scanf("%d%d", &po[i].l, &po[i].r);
if(po[i].r > n) po[i].r = n;
temp.emplace(po[i].l), temp.emplace(po[i].r);
}
it = temp.begin();
int cur = *it;
for(it = temp.begin(); it != temp.end(); it++){
a.push_back(*it);
if(*it - cur > 1) a.push_back(*it-1);
cur = *it;
}
sort(a.begin(), a.end());
tree.resize(2*a.size()+1);
build(1, 1, a.size());
for(int i = 1; i <= m; i++){
int ll = lower_bound(a.begin(), a.end(), po[i].l)-a.begin();
int rr = lower_bound(a.begin(), a.end(), po[i].r)-a.begin();
dye(1, ll, rr, co++);
}
query(1, 1, a.size());
printf("%d", ans);
return 0;
}