记录编号	610261	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[HAOI 2014]贴海报	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.261 s
提交时间	2025-12-18 23:07:47	内存使用	11.49 MiB

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int a[N], lazy[N], n, c;

set<int> cnt;

void update(int rt, int l, int r, int L, int R, int x) {
    if (L > r || R < l) return;
    if (L <= l && r <= R) {
        lazy[rt] = x;
        a[rt] = x;
        return;
    }
    int mid = (l + r) / 2;
    if (lazy[rt]) {
        lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
        a[rt * 2] = a[rt * 2 + 1] = lazy[rt];
        lazy[rt] = 0;
    }
    update(rt * 2, l, mid, L, R, x);
    update(rt * 2 + 1, mid + 1, r, L, R, x);
}

void query(int rt, int l, int r) {
    if (l == r) {
        if (a[rt]) cnt.insert(a[rt]);
        return;
    }
    int mid = (l + r) / 2;
    if (lazy[rt]) {
        lazy[rt * 2] = lazy[rt * 2 + 1] = lazy[rt];
        a[rt * 2] = a[rt * 2 + 1] = lazy[rt];
        lazy[rt] = 0;
    }
    query(rt * 2, l, mid);
    query(rt * 2 + 1, mid + 1, r);
}

int l[N], r[N];

int main() {
    int c;
        cin >> c >> n;
        memset(a, 0, sizeof(a));
        memset(lazy, 0, sizeof(lazy));
        set<int> uniq;
        map<int, int> d;
        for (int i = 1; i <= n; i++) {
            cin >> l[i] >> r[i];
            uniq.insert(l[i]);
            uniq.insert(r[i]);
            uniq.insert(l[i] - 1);
            uniq.insert(r[i] + 1);
        }
        int now = 0;
        for (auto x: uniq) {
            d[x] = ++ now;
        }
        for (int i = 1; i <= n; i++) {
            l[i] = d[l[i]];
            r[i] = d[r[i]];
            update(1, 1, now, l[i], r[i], i);
        }
        cnt.clear();
        query(1, 1, now);
        cout << cnt.size() << endl;

    return 0;
}