1.模拟（暴力）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
bool st[N];

int main()
{
    scanf("%d%d", &m, &n);
    while (n -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        for (int i = l; i <= r; i ++ ) st[i] = true;
    }

    int res = 0;
    for (int i = 0; i <= m; i ++ )
        if (!st[i])
            res ++ ;

    printf("%d\n", res);

    return 0;
}

2.区间合并

#include <bits/stdc++.h>

using namespace std;

int L, m;
struct A {
    int a, b;
} a[1010];

bool cmp(const A &x, const A &y) {
    return x.a < y.a;
}

int main() {
    cin >> L >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].a >> a[i].b;
    }
    sort(a + 1, a + m + 1, cmp);
    int t = a[1].b - a[1].a + 1, r = a[1].b;
    for (int i = 2; i <= m; i++) {
        if (a[i].a >= r) {
            t += a[i].b - a[i].a + 1;
            r = a[i].b;
        }
        if (a[i].a <= r && a[i].b > r) {
            t += a[i].b - r;
            r = a[i].b;
        }
    }
    cout << L - t + 1;

    return 0;
}

3.STL(set)改写

#include<bits/stdc++.h>

using namespace std;

int L, m;
set<pair<int, int>> intervals;

int main() {
    cin >> L >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        intervals.insert(make_pair(a, b));
    }
    int t = 0, r = -1;
    for (auto interval: intervals) {
        int a = interval.first;
        int b = interval.second;
        if (a > r) {
            t += b - a + 1;
            r = b;
        } else if (a <= r && b > r) {
            t += b - r;
            r = b;
        }
    }
    cout << L - t + 1;

    return 0;
}

4.线段树

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

struct Node {
    int l, r; // 区间左右边界
    int cover; // 区间覆盖次数
    int cnt; // 区间中未被覆盖的长度
};

vector <Node> tree(4000002);

void build(int node, int l, int r) {
    tree[node].l = l;
    tree[node].r = r;
    tree[node].cover = 0;
    tree[node].cnt = r - l + 1;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
}

void update(int node, int l, int r, int val) {
    if (tree[node].l >= l && tree[node].r <= r) {
        tree[node].cover += val;
        if (tree[node].cover > 0) {
            tree[node].cnt = 0;
        } else {
            if (tree[node].l == tree[node].r) {
                tree[node].cnt = 1;
            } else {
                tree[node].cnt = tree[node * 2].cnt + tree[node * 2 + 1].cnt;
            }
        }
        return;
    }
    int mid = (tree[node].l + tree[node].r) / 2;
    if (l <= mid) {
        update(node * 2, l, r, val);
    }
    if (r > mid) {
        update(node * 2 + 1, l, r, val);
    }
    if (tree[node].cover > 0) {
        tree[node].cnt = 0;
    } else {
        tree[node].cnt = tree[node * 2].cnt + tree[node * 2 + 1].cnt;
    }
}

int main() {
    int L, m;
    cin >> L >> m;
    build(1, 0, L);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        update(1, a, b, 1);
    }
    cout << tree[1].cnt;

    return 0;
}

5.差分

#include <bits/stdc++.h>

using namespace std;

int L, m;
vector<int> diff(1000002, 0);

int main() {
    cin >> L >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        diff[a]++;
        diff[b + 1]--;
    }
    int t = 0, r = 0;
    for (int i = 0; i <= L; i++) {
        r += diff[i];
        if (r == 0) {
            t++;
        }
    }
    cout << t;

    return 0;
}