POJ 3667 Hotel ( 线段树区间合并 )

题目链接~~>

做题感悟：这题是接触线段树区间合并的第一题，做的很纠结。

解题思路：

                注意线段树上节点代表的信息 ： 每个节点需要维护 lc , rc , mc ,add ,见下图：

add 为懒惰标记。假设 i 代表父亲节点编号，左儿子为  i * 2  ，右儿子为 i * 2  + 1 ,那么我们可以得到 ： T [ i ] .lc 首先加上左儿子的左边的空格数，然后需要判断一下，如果左儿子的左节点占满了整个左区间时需要再加上右儿子的左边的空格数。同理 T [ i ] .rc 也可以这样得到。那么 mc 怎样维护呢 ？ 无非是左儿子的 mc  ,右儿子的 mc .不要忘记左儿子的右区间 + 右儿子的左区间也可以。这样就可以了。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      #define L(x) (x * 2)
     
    
   

    

     

    
    

     

      #define R(x) (x * 2 + 1)
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const int mod = 1000000007 ;
     
    
   

    

     

    
    

     

      const int MY = (1<<5) + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 50000 + 5 ;
     
    
   

    

     

    
    

     

      const int S = 20 ;
     
    
   

    

     

    
    

     

      int n ,m ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int le ,rt ,add ;
     
    
   

    

     

    
    

     
 int lc ,rc ,mc ;
     
    
   

    

     

    
    

     

      }T[MX<<2] ;
     
    
   

    

     

    
    

     

      void build(int i ,int le ,int rt) // 建树
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       T[i].le = le ;
     
    
   

    

     

    
    

     

       T[i].rt = rt ;
     
    
   

    

     

    
    

     

       T[i].add = -1 ;
     
    
   

    

     

    
    

     

       T[i].lc = T[i].rc = T[i].mc = rt - le + 1 ;
     
    
   

    

     

    
    

     
 if(le == rt)  return ;
     
    
   

    

     

    
    

     
 int Mid = (le + rt)>>1 ;
     
    
   

    

     

    
    

     

       build(L(i) ,le ,Mid) ;
     
    
   

    

     

    
    

     

       build(R(i) ,Mid+1 ,rt) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void push_down(int i) // 向下更新
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(T[i].add != -1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int Mid = (T[i].rt + T[i].le)>>1 ;
     
    
   

    

     

    
    

     

       T[L(i)].add = T[R(i)].add = T[i].add ;
     
    
   

    

     

    
    

     

       T[L(i)].lc = T[L(i)].rc = T[L(i)].mc = T[i].add ? 0 : (Mid - T[i].le + 1) ;
     
    
   

    

     

    
    

     

       T[R(i)].lc = T[R(i)].rc = T[R(i)].mc = T[i].add ? 0 : (T[i].rt - Mid) ;
     
    
   

    

     

    
    

     

       T[i].add = -1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void push_up(int i) // 向上回溯
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       T[i].lc = T[L(i)].lc ;
     
    
   

    

     

    
    

     

       T[i].rc = T[R(i)].rc ;
     
    
   

    

     

    
    

     
 if(T[L(i)].lc == T[L(i)].rt - T[L(i)].le + 1) //
     
    
   

    

     

    
    

     

       T[i].lc += T[R(i)].lc ;
     
    
   

    

     

    
    

     
 if(T[R(i)].rc == T[R(i)].rt - T[R(i)].le + 1)
     
    
   

    

     

    
    

     

       T[i].rc += T[L(i)].rc ;
     
    
   

    

     

    
    

     

       T[i].mc = max(max(T[L(i)].mc ,T[R(i)].mc) ,T[L(i)].rc + T[R(i)].lc) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void section(int i ,int le ,int rt ,int add) // 区间更新
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(T[i].le == le && T[i].rt == rt)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       T[i].add = add ;
     
    
   

    

     

    
    

     

       T[i].lc = T[i].rc = T[i].mc = add ? 0 : (T[i].rt - T[i].le + 1) ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       push_down(i) ;
     
    
   

    

     

    
    

     
 int Mid = (T[i].le + T[i].rt)>>1 ;
     
    
   

    

     

    
    

     
 if(le > Mid)   section(R(i) ,le ,rt ,add) ;
     
    
   

    

     

    
    

     
 else if(rt <= Mid)   section(L(i) ,le ,rt ,add) ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       section(L(i) ,le ,Mid ,add) ;
     
    
   

    

     

    
    

     

       section(R(i) ,Mid+1 ,rt ,add) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       push_up(i) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Query(int i ,int Len) // 查询最左边的编号
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(T[i].le == T[i].rt)
     
    
   

    

     

    
    

     
 return 1 ;
     
    
   

    

     

    
    

     

       push_down(i) ;
     
    
   

    

     

    
    

     
 int Mid = (T[i].le + T[i].rt)>>1 ;
     
    
   

    

     

    
    

     
 if(T[L(i)].mc >= Len)   // 进入左区间
     
    
   

    

     

    
    

     
 return   Query(L(i) ,Len) ;
     
    
   

    

     

    
    

     
 else if(T[L(i)].rc + T[R(i)].lc >= Len)
     
    
   

    

     

    
    

     
 return Mid - T[L(i)].rc + 1 ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 return Query(R(i) ,Len) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 int pos ,x ,L ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&m))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       build(1 ,1 ,n) ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < m ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d" ,&pos) ;
     
    
   

    

     

    
    

     
 if(pos == 1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d" ,&L) ; // 长度
     
    
   

    

     

    
    

     
 if(T[1].mc < L)
     
    
   

    

     

    
    

     
 puts("0") ;
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       x = Query(1 ,L) ;  // 查找最左边的编号
     
    
   

    

     

    
    

     
 printf("%d\n" ,x) ;
     
    
   

    

     

    
    

     

       section(1 ,x ,x+L-1 ,1) ; // 占满
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d%d" ,&x ,&L) ; // 清空
     
    
   

    

     

    
    

     

       section(1 ,x ,x+L-1 ,0) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/41082019