（其实这题还可以用分块和树状数组来写）

题解

解法一：区间合并
将区间按左端点升序排序，然后模拟一遍，若下一个区间在当前区间内部，则忽略，若相交，更新ed值，若下一个区间的左端点在区间外，则统计点的个数，然后更新st和ed即可，最后在循环外面处理剩下的区间输出即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
typedef pair<int, int> pii;

pii arr[N];
int main() {
    int l, m;
    cin >> l >> m;
    for(int i = 0; i < m; i++) cin >> arr[i].first >> arr[i].second;
    sort(arr, arr + m);
    int cnt = 0, st = arr[0].first, ed = arr[0].second;
    for(int i = 1; i < m; i++) {
        if(arr[i].first >= ed)  {
            cnt += ed - st + 1;
            st = arr[i].first, ed = arr[i].second;
        } else {
            ed = max(ed, arr[i].second);
        }
    }
    cnt += ed - st + 1;
    cout << l + 1 - cnt << endl;
    return 0;
}

解法二：线段树

线段树板子题，把所有点的初始值都赋值为1，update后赋值为0，因为统计所有区间，所以输出tree[1].sum即可。

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

const int N = 1e4 + 10;
struct Tree
{
    int l, r;
    int sum;
} tree[N << 2];

void build(int root, int l, int r)
{
    tree[root].l = l, tree[root].r = r;
    if (l == r)
    {
        tree[root].sum = 1; 
        return;           
    }
    int mid = (l + r) / 2;
    build(root * 2, l, mid);            
    build(root * 2 + 1, mid + 1, r); 
    tree[root].sum = tree[root * 2].sum + tree[root * 2 + 1].sum;
}

void update(int root, int l, int r, int x, int y)
{
    if (l > y || r < x || tree[root].sum == 0) return;
    if (x <= l && y >= r)
    {
        tree[root].sum = 0; 
        return;
    }
    int mid = (l + r) >> 1;    
    update(root << 1, l, mid, x, y);
    update(root << 1 | 1, mid + 1, r, x, y);
    tree[root].sum = tree[root * 2].sum + tree[root * 2 + 1].sum;
}
int main()
{
    int L, M, x, y;
    cin >> L >> M;
    build(1, 1, L + 1);
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y;
        update(1, 1, L + 1, x + 1, y + 1);
    }
    printf("%d\n", tree[1].sum);
    return 0;
}

解法三：珂朵莉树

珂朵莉树是一种基于set的暴力数据结构,珂朵莉树的关键在于推平一段区间，即把一段区间的数变的一样,对每一个点建立一个集合, 当修改时，把要修改区间分成两部分，一部分是需要修改的，一部分是不需要修改的，返回需要修改的地址(这里返回迭代器)，然后把这一段区间内所有的集合都删掉，用一个大集合替代，不断操作，即可得到答案。

#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int l, r, v;
    Node() {}
    Node(int L, int R = -1, int V = 0) : l(L), r(R), v(V) {}
    const bool operator < (const Node &x) const { 
        return l < x.l; 
    }
};

int l, m, x, y, sum;
set<Node> s;
typedef set<Node>::iterator IT;

IT split(int pos)
{
    IT it = s.lower_bound(Node(pos));
    if (it != s.end() && it->l == pos)
        return it;
    --it;
    int L = it->l, R = it->r, V = it->v;
    s.erase(it);
    s.insert(Node(L, pos - 1, V));
    return s.insert(Node(pos, R, V)).first;
}

void remove(int l, int r)
{
    IT itl = split(l), itr = split(r + 1);
    s.erase(itl, itr);
    s.insert(Node(l, r, 0));
}

int get_sum()
{
    for (IT it = s.begin(); it != s.end(); ++it)
        sum += it->v * (it->r - it->l + 1);
    return sum;
}

int main()
{
    cin >> l >> m;
    s.insert(Node(0, l, 1));
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y;
        remove(x, y);
    }
    printf("%d", get_sum());
}