来看一个很简单的方法,因为不会复杂的/(ㄒoㄒ)/~~
首先定义一个数组s[l+1],注意有l+1棵树,初始化为0,之后在for循环内,在修建筑范围内s[i]变为1,最后只要看一下s[l+1]内还有多少0就可以了
#include<iostream>
using namespace std;
int main()
{
int a,b,t=0,l,m;
scanf("%d %d",&l,&m);
int s[l+1]={0};//初始化为0
for(int i=1;i<=m;i++){//m组数
scanf("%d %d",&a,&b);//输入数据
for(int j=a;j<=b;j++)
s[j]=1;//在a到b的范围内通通变为1
}
for(int i=0;i<=l;i++){//注意有l+1次
if(s[i]==0)
t++;//统计还有多少0
}
printf("%d",t);//最后输出
return 0;
}
虽然代码是简单的,但是时间复杂度是$O(nm)$呀,用差分是$O(n+m)$线段树是$O(n+mlogn)$