算法1
(差分) $O(n)$
我们把数组$a_1, a_2, a_3, , , a_n$变成$a_1, a_2-a_1, a_3-a_2,,,,,,a_n-a_{n-1}$,这样对原数组的一个区间修改,就可以转化成在差分数组的两个点上的修改。
例如,你对原数组的$a_1到a_3加1$进行修改,你可以在差分数组的$b_1$处-1,在差分数组$b_4$处加1,再对差分数组求前缀和就能得到原数组。
时间复杂度
$O(n)$,因为每一个区间操作转化成对两个端点的操作。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[10010];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++){
int l, r;
cin >> l >> r;
a[l]--;
a[r+1]++;
}
a[0] += 1;
for(int i = 1; i <= n; i++){
a[i] += a[i-1];
}
int ans = 0;
for(int i = 0; i <= n; i++){
if(a[i] > 0){
ans++;
}
}
cout << ans << "\n";
return 0;
}