题解 | 校门外的树 | 差分法

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int len;cin>>len;
    vector<int> diffs(2+len,0);
    int tests;cin>>tests;
    while(tests--){
        int left,right;cin>>left>>right;
        ++diffs[left],--diffs[1+right];
    }

    int remaining=0;
    int cover=0;
    for(int i=0;i<=len;++i){
        cover+=diffs[i];
        remaining+=(cover==0);
    }

    cout<<remaining<<'\n';

    return 0;
}