题解 | #校门外的树#

看了很久别人的代码才看明白，原来这道题用的是差分的思想 我原本直接用的是将这些树用一个数组表示，把选中区域的树的值变为1，没被选中的就为0，最后遍历输出值为0的树数量即为最终答案，但是通过率仅为20%，不知到为什么。下面是我错误的代码，希望有大神帮我看一下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int l,m,sum=0;
    cin>>l>>m;
    int leng[10005];
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        for(int j=a;j<=b;j++){
            leng[j]=1;
        }
    }
    for(int i=0;i<=l;i++){
        if(leng[i]==0)
            sum++;
    }
    cout<<sum;
}

看了别人的解题，其实就是用的差值，数组a[]记录的是当前元素跟上一个元素的差值，一开始元素都为0，差值也为0，选中区域后，让这片区域的值加一，那这区域的左端点a[i]就会比a[i-1]的值多一，右端点a[j]就会比a[j+1]多一，差值也就多一，但是区域内部都加一了，所以差值是没变的，只用管两边端点即可。

for(int i=1;i<=m;i++){
        cin>>x>>y;
        a[x]+=1;
        a[y+1]-=1;
    }

上面这段代码就是用来把元素之间的差值全部记起来，然后用这些差值计算出每一个元素的值，不是0的说明他被区域覆盖了，他的值代表有多少个区域套住了他，我们不要管，只用管等于0的有多少个，因为0的是剩余的。

for(int i=0;i<=l;++i){
        a[i]+=a[i-1];
        if(!a[i]) ++sum;
    }

总代码：

```#include<bits/stdc++.h>
using namespace std;
int a[10005],sum;
int main(){
    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]) ++sum;
    }
    cout<<sum<<endl;
    return 0;
}