题目描述
略
样例
略
算法1
(差分)
看了几篇题解没人用差分,有点奇怪,所以补一个差分代码.......
时间复杂度
O(n)
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int b[N];
void insert(int l, int r)
{
b[l] -= 1;
b[r + 1] += 1;
}
int main()
{
int l, m;
cin >> l >> m;
for (int i = 0, x, y; i < m; ++ i)
{
cin >> x >> y;
insert(x, y);
}
for (int i = 1; i <= l; ++ i) b[i] += b[i - 1];
int res = 0;
for (int i = 0; i <= l; ++ i)
{
if (!b[i]) res ++;
}
cout << res << endl;
return 0;
}