校门外的树 （C++代码）

解题思路:

为何要用线段树？只是为了炫耀你们的学识吗？用树状数组难道不是更好吗？

思路：树状数组的经典应用二：区间更新、单点查询，维护的是数列的差分数组（t[i]=a[i]-a[i-1]），区间加就显得很方便，log n 求一遍前缀和就是单点查询了了，巧妙的转化了问题。

唯一需要注意的点是，由于二进制的特殊性，树状数组中 0 下标是不能用的，然而这道题需要 0，所以我们需要将整个树状数组向右平移一位。

注意事项:





参考代码:

#include<cstdio>int l,t[10005];//树状数组经典函数，没什么好说的

void add(int x,int y){    

if(!x)return;    

for(;x<=l+1;x+=x&-x)//平移一位        

t[x]+=y; }

int query(int x)

{    int s=0;    

for(;x;x-=x&-x)        

s+=t[x];    

return s; }

int main(){    

int m,x,y;    

scanf("%d%d",&l,&m);    

while(m--)    {       

 scanf("%d%d",&x,&y);       

 add(x+1,1);//原来应该是 [x..n]++, [y+1..n]-- 实现区间加，这里平移一位以凸显 0，无伤大雅。        

add(y+2,-1);   

 }   

 int ans=0;    

for(int i=1;i<=l+1;i++)//同样 [0..l] 平移至 [1..l+1]       

 ans+=query(i)==0;//如果为 0 则说明这里没有被砍伐过，累计入答案    

printf("%d\n",ans);    return 0; 

}