差分,时间复杂度O(n),附上差分小板子
算法1
想象成区间涂颜色,不过本题是问你有多少区间没被图上,差分一下就好啦
时间复杂度
O(n)
C++ 代码
#include <cstdio>
#include <algorithm>
using namespace std;
const int M = 1e5 + 10;
int dif[M], arr[M], res[M];
//差分板子
void change(int l, int r, int v) {// [l, r] + v
dif[l] += v, dif[r + 1] -= v;
}
//初始化
void init(int n) {
dif[1] = arr[1];
for (int i = 2; i <= n; ++i) dif[i] = arr[i] - arr[i - 1];
}
// 求最终结果
void get_res(int n) {
res[1] = dif[1];
for (int i = 2; i <= n; ++i) {
res[i] = dif[i] + res[i - 1];
}
}
int main() {
int L, m;
scanf("%d %d\n", &L, &m);
for (int i = 0; i < m; ++i) {
int l, r;
scanf("%d %d\n", &l, &r);
change(l + 1, r + 1, 1); // 方便起见l和r都+1
}
get_res(L + 1);
int ans = 0;
for (int i = 1; i <= L + 1; ++i) ans += (res[i] == 0);//计算没被图颜色的点
printf("%d", ans);
return 0;
}