题目链接：

总时间限制:

1000ms

内存限制:

65536kB

描述

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。

马路上有一些区域要用来建地铁，这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入

输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出

输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

样例输入

500 3150 300100 200470 471

样例输出

298

来源

noip2005普及组

这个题真是非常适合用来入门了，之前也做过线段树的专题，没做笔记，到现在快忘干净了，，，做笔记很重要额。。。

看代码吧，写的还算详细。当然这个题也可以通过标记来实现，耗费的时间差不多。（第一个是用线段树写的，第二个是用标记写的）

线段树代码：

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int maxn = 10010*4; 5 struct Tree 6 { 7     int l,r; 8     int sum; 9 }tree[maxn];10 11 void build(int rt,int ll,int rr)12 {13     tree[rt].l = ll;14     tree[rt].r = rr;15     if(ll == rr) //左右节点相等说明到了叶子节点了16     {17         tree[rt].sum = 1;// 这个节点最开始只有一棵树18         return ;    //不写return会炸19     }20     int mid = (ll+rr)/2;21     build(rt*2,ll,mid); //向左建立左子树22     build(rt*2+1,mid+1,rr); //向右建立右子树23     //父亲节点树的棵数是左右子节点树的棵数的和24     tree[rt].sum = tree[rt*2].sum + tree[rt*2+1].sum;25 }26 27 void update(int rt,int ll,int rr,int x,int y)28 {29     if(ll>y||rr
        
         =rr)32     {33         tree[rt].sum = 0; //将此区间树拔光34         return ;35     }36     int mid = (ll+rr)/2; //别取成要查找区间的中止了，写错了找了好久的bug37     update(rt*2,ll,mid,x,y); //二分寻找[ll,rr]，使其与[x,y]有交集；38     update(rt*2+1,mid+1,rr,x,y);39     tree[rt].sum = tree[rt*2].sum + tree[rt*2+1].sum;40 }41 int main()42 {43     int L,M;44     int x,y;45 //    scanf("%d%d",&L,&M);46     cin>>L>>M;47     build(1,1,L+1);48     for(int i=0;i
         
          >x>>y;52         update(1,1,L+1,x+1,y+1);53     }54     int ans = tree[1].sum;55     printf("%d\n",ans);56     return 0;57 }
         
        
       
      

标记代码：

1 #include
      
        2 #include
       
         3 #include 
        
          4 using namespace std; 5  6 const int maxn = 10010; 7 int L,M; 8 int x,y; 9 int sum;10 int maze[maxn]; //将某段区间内的值全部标记为1；11 12 int main()13 {14     while(scanf("%d%d",&L,&M)!=EOF)15     {16         memset(maze,0,sizeof(maze));17         sum = 0;18         for(int i=0;i
         
          >x>>y;21             for(int ii = x;ii<=y;ii++)22             {23                 if(maze[ii]==1)24                     continue;25                 maze[ii] = 1;26             }27         }28         for(int i=0;i<=L;i++)29         {30             if(maze[i] == 0)  //统计不是0的个数，也就是剩余的树的数目；31                 sum++;32         }33         cout<
          
           <