算法1
(前缀和) $O(M+L)$
我们可以把每一次移除区域中的树看作这一区域的树的数量减1,这样我们可以利用前缀和的算法解决问题,最终求出的前缀和数列中值为0的点即为有树的点。
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 10010;
int q[N];
int l, m, res;
int main()
{
cin >> l >> m;
while(m -- )
{
int a, b;
cin >> a >> b;
q[a] += -1, q[b+1] += 1;
}
for(int i = 1; i <= l; i ++ ) q[i] += q[i-1];
for(int i = 0; i <= l; i ++ )
if(q[i] == 0) res ++ ;
printf("%d", res);
return 0;
}