题解 | #剩下的树#

/*
	将所有区间存在数组中，并以左端点升序排序
	排序后将重叠部分合并
	依次减去合并后的区间长度，便是最终结果
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct qujian{
    int left, right;
    qujian(int a, int b) : left(a), right(b){}
};

bool cmp(qujian a, qujian b) {
    return a.left < b.left;
}

int main()
{
    int L, M;
    while(cin >> L >> M) {
        vector<qujian> movedtree;
        for(int i = 0; i < M; i++) {
            int left, right;
            cin >> left >> right;
            movedtree.push_back(qujian(left, right));
        }
        sort(movedtree.begin(), movedtree.end(), cmp); // 以左端点升序排序
        for(int k = 1; k < movedtree.size(); k++) {    // 将重叠部分合并
            if(movedtree[k].left <= movedtree[k - 1].right) {
                movedtree[k].left = movedtree[k - 1].left;
                if(movedtree[k-1].right > movedtree[k].right) {
                    movedtree[k].right = movedtree[k-1].right;
                }
                movedtree[k - 1].left = 0;
                movedtree[k - 1].right = -1;
            }
        }
        L += 1;
        for(int g = 0; g < movedtree.size(); g++) {  // 依次减去合并后的区间长度，便是最终结果

            L -= movedtree[g].right - movedtree[g].left + 1;
        }
        cout << L << endl;
    }
    return 0;
}