值周

差分与前缀和

技巧介绍：

前缀和：

sum[0]=a[0]

sum[1]=a[0]+a[1]------>sum[1]=sum[0]+a[1]

sum[2]=a[0]+a[1]+a[2]------>sum[2]=sum[1]+a[2]

sum[3]=a[0]+a[1]+a[2]+a[3]------>sum[3]=sum[2]+a[3]

.........

前缀和就是类似与求数列前n项和，因此对上述进行归纳即可得到

sum[i]=sum[i-1]+a[i]

差分：

d[1]=a[1]-a[0]=a[1]-0=a[1]

d[2]=a[2]-a[1]

d[3]=a[3]-a[2]

这时要想表示每一项a[i]即可对d[i]求前缀和

d[1]+d[2]=a[1]-a[0]+a[2]-a[1]="a[2]"

d[1]+d[2]+d[3]=a[2]+a[3]-a[2]="a[3]"

即a[i]=a[i-1]+d[i];

差分的作用： 对区间的数进行修改，可以只改变区间端点的值即可

链接：https://ac.nowcoder.com/acm/contest/27269/F 来源：牛客网

using namespace std;
int d[100000010],sum[100000010];
int main(){
    long long l,m,s=0;
    cin>>l>>m;
    while(m--){
        long long a,b;
        cin>>a>>b;
        if(a>b)swap(a,b);
        d[a]+=1;//对区间两端点进行操作，即对该区间内所有值进行修改（加上或减去某一个值）
        d[b+1]-=1;
    }
    sum[0]+=d[0];//非常重要！！！
    for(int i=1;i<=l;i++){
        sum[i]=sum[i-1]+d[i];//求前缀和
    }
    for(int i=0;i<=l;i++){
        if(sum[i]){
            s++;
        }
    }
    cout<<l+1-s;
    return 0;
}