前言

• 前缀和和差分是一对对称的操作，对前缀和数组差分可以得到原数组，对差分数组前缀和也可以得到原数组

题意

• 一条长为L线段等距离分布L+1个点，每次去掉一段中的所有点，去除m次后还剩多少点

思路

• 第一种思路：差分查询次数，统计当前点被查询的次数和上一个点被查询的次数的差，再前缀和，可求出每一个点被查询的次数，如果次数为0，说明没被查询过。

• 第二种思路：合并区间，把所有区间按左界排序，遍历，若当前区间左界小于合并区间右界，加入合并，更新合并区间右界为max(当前区间右界，合并区间右界)，托当前区间左界大于合并区间左界，答案+=合并区间长度，然后开始新的合并区间。

  注意：这种思路并未更新最后一个区间，所以遍历完所有区间后，需要把最后一个合并区间单独加上。

• 第三种思路：离散化，由题意，查询的区间很短，总区间很长，所以我们可以只记录发生变化的区间，具体来说，一个需要加入答案的区间，一定满足，右界是由查询0次变为查询1次的次的分界点

• 所以我们直接存所有点，按照点位置进行一次排序，遍历所有点，如果某个点是一个区间的开始（由0变为1），就将当前点到上一个点种所有的点加入ans。

代码

• 思路一

#include<bits/stdc++.h>
using namespace std;
int a[101010100];
int main(){
    int L,m;
    int sum=0;
    long long ans=0;
    cin>>L>>m;
    for(int i=0;i<=L;i++){
        int l,r;
        cin>>l>>r;
        a[l]--;
        a[r+1]++;
    }
    for(int i=0;i<=L;i++){
        sum+=a[i];
        if(sum==0)ans++;
    }
    cout<<ans;
}

• 思路三

#include<bits/stdc++.h>
using namespace std;
struct ps{
    int num;
    int pos;
}a[300000];
bool cmp(ps a,ps b){
    if(a.pos==b.pos) return a.num<b.num;
    if(a.pos<b.pos) return 1;
    return 0;
}
int main(){
    int L,n;
    scanf("%d%d",&L,&n);
    for(int i=1;i<=n;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        a[i].pos=l;
        a[i+n].pos=r+1;
        a[i].num=1;
        a[i+n].num=-1;
    }
    sort(a+1,a+1+2*n,cmp);
    int jg=0;
    int ans=0;
    for(int i=1;i<=2*n;i++){
        jg+=a[i].num;
        if(jg==1&&a[i].num==1)ans+=a[i].pos-a[i-1].pos;
    }
    ans+=L-a[2*n].pos+1;
    printf("%d",ans);
    return 0;
}