c++差分数组解法

解题思路:
这题用数组标记法是可以做的，但可以进一步来降低时间复杂度，不难看出数组标记法中，每一步中都需要对区间内赋值为1，这一步与给区间内加上一个增量的操作等价，可以使用差分数组。

这里给小白科普一下差分数组：

给定数组 a[]，需要在某个区间 [l, r] 内的所有元素增加一个常量值 v。

diff[l] += v;
diff[r + 1] -= v;

例如 a[5] = { 1, 5, 8, 9, 6 } diff[5] = { 1, 4, 3, 1, -3 }

对a数组在[1, 3]区间内数加2（假设下标从0开始）

即diff[1]+=2 diff[4]-=2

可以修改后的差分数组为 diff[5] = { 1, 6, 3, 1, -5 }

这时候只需要对diff[]求前缀和，就可以得出a[]修改后的值为a[5] = { 1, 7, 10, 11, 6 }

注意事项:
题中的L容易和区间左端点l写成一个，导致编译器报错

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int a[N],L,M,l,r,tmp,cnt;

int main(){
    cin>>L>>M;
    while(M--){
        cin>>l>>r;
        a[l]++;
        a[r+1]--;
    }
    for(int i=0;i<=L;i++){
        tmp+=a[i];
        if(tmp==0) cnt++;
    }
    cout<<cnt;
    return 0;
}