校门外的树_牛客博客

思路：
能暴力就先先一下暴力，题目差不多就会一半了。
1.每次输入左右区间就把数组对应位置+1表示这棵树被移走，重复的部分多次+1不要紧，我们的结果是有多少个元素值是0。
2. $O(L*M)$ ，好像不会超时，考虑更优的做法。
差分+前缀和
1.给一个区间加上一个值，我们只要考虑两个端点，中间的元素不需要考虑。
2.前缀和 $a[i]=a[i-1]+a[i]$ ，理解为第 $i$ 位的值比第 $i-1$ 位大 $a[i]$ 。
3，接着考虑区间赋值的问题，区间 $[L,R]$ 加上1，那么第L个位置比第L-1个位置大1，第R+1个位置比第R个位置小1，所以可以先预处理 $a[L]+=1,a[R+1]-=1;$ ，最后再一遍前缀和得到最终的数组，里面0的个数就是剩余树的个数。
想过离散化，挺有意义的，数据也不大，懒得写了，鸽了。
Code:

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
int a[10005],ans;
int main() {
    js; int l,m,x,y;
    cin>>l>>m;
    for(int i=1;i<=m;++i) {
        cin>>x>>y;
        a[x]+=1;
        a[y+1]-=1;
    }
    for(int i=0;i<=l;++i) {
        a[i]+=a[i-1];
        if(!a[i])    ++ans;
    }
    cout<<ans<<endl;
    return 0;
}