简单易懂 应对多次操作的差分组解法

这道题我做过很多次了。。。
各种各样的变种，决定总结一下

首先读题，题意很清晰明了，就是把从a到b的树砍光，之后反复重复m次，每次的a，b都会变化
因此第一种朴素的想法诞生了。。。
将有树的位置用数组标记为0，一但进行砍伐活动，就将从a到b的所有数都加上1
最后一次砍伐结束后去遍历数组，看数组中有几个0
例子：
数组a一开始初始化全为0
第一次砍伐1-3
a[0] a[1] a[2] a[3] a[4] a[5] …
0 1 1 1 0 0

第二次砍伐2-5
a[0] a[1] a[2] a[3] a[4] a[5] …
0 1 2 2 1 1

依次类推
解法一的代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int l,r,m,len,ans;
int i,j;
int a[10005],c[10005];
int main()
{
    cin>>len>>m;
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        for(j=l;j<=r;j++) a[j]++;
    }
    for(i=0;i<=len;i++)
    {
        if(a[i]==0) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

这种方法很好理解，编写过程也较为简单，但我并不建议这样解决问题，因为这道题的数据范围很小 m竟然只有100！！！

这道题的变种m往往会达到一个极大的数值比如1000000或者更多，在这种情况下上面的方法就会超时因为询问的次数过多，同时每次从a到b遍历赋值的过程过于繁琐
对这道题进行更加深入的分析，可以发现实质进行的操作是在对一个区间的所有数进行加减操作，这个操作可以使用线段树实现，但是在这道题中，可以使用差分组进行运算
差分数组指的是当前数组与前一个数组进行做差，并储存在新的数组中
公式即 c[i]=a[i]-a[i-1]（公式不唯一）

例子：
a[i] 0 0 0 0 0
c[i] 0 0 0 0 0

砍伐1-3
a[i] 0 1 1 1 0
c[i] 0 1 0 0 -1

从这个例子可以看出在对一个区间进行加减操作时只需要变化c[a]和c[b+1] 即可
在得出变化后的差分组后，可反向推导公式
a[i]=c[i]+a[i-1]
只需要遍历一次就可以解决问题，成倍的提高效率。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int l,r,m,len,ans;
int i,j;
int a[10005],c[10005];
int main()
{
    cin>>len>>m;
    for(i=1;i<=m;i++)
    {
        cin>>l>>r;
        c[l]++;
        c[r+1]--;
    }
    a[0]=c[0];
    for(i=1;i<=len;i++)
    {
        a[i]=a[i-1]+c[i];
    }
    for(i=0;i<=len;i++)
    {
        if(a[i]==0) ans++;
    }
    cout<<ans<<endl;
    return 0;
}