值周

使用差分数组对序列进行区间修改

对于这种区间很长，然后整个区间整个区间进行加减的，要想到使用差分数组，即对数组的区间进行操作，只有端点处的差分值发生了变化，区间之间的差分值没有发生变化，从而整区间地进行操作。 这题还可想到，因为差分值d[0]表示的是a[1]-a[0]，这样的话a[0]的值就无法记录。我们可以想象a[0]前面有个不变的0，这样d[0]就等于a[0]-0，从而a[0]也能被记录下来了。

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