算法

• 枚举

•  前缀和，差分

前缀和：sum[ i ] = a[ i ] + sum[i - 1]  前 i 个数的求和。

差分：delta[ i ] = a[ i ] - a[ i -1 ] 第 i 个数 - 第 i-1 个数。

例题：https://ac.nowcoder.com/acm/problem/16649

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 /**
 4 对于区间问题，简化成区间端点的问题；
 5 比如： 前缀和 或者 差分，利用端点既可以维护整个数组，降低时间复杂度
 6 */
 7 int L,M,cnt;
 8 int delta[10010]; //差分数组
 9 
10 int main()
11 {
12     cin>>L>>M;
13     while(M--)
14     {
15         int l,r;
16         scanf("%d%d",&l,&r);
17         if(l>r) swap(l, r);
18         delta[l]++;    //更新差分数组的值
19         delta[r+1]--;
20     }
21     int a=0;//只需要单个的a就可以得到a[i]每一个位置的值，但我们不需要保存，只需要判断a[i]==0即可
22     for(int i=0;i<=L;i++)
23     {
24         a+=delta[i];
25         if(a==0)
26             cnt++;
27     }
28     cout<<cnt;
29     return 0;
30 }