NYOJ250 ROOM ASSIGNATION || POJ3667 Hotel

  1 /*
  2   Name: 
  3   Copyright: 
  4   Author: 
  5   Date: 28/04/13 21:55
  6   Description: 
  7         刚开始做这道题的时候，第一感觉用线段树应该很容易实现，结果发现我没做过此类的线段树题目
  8         然后上网看了别人的代码，才了有点思路，现总结如下：
  9         这道题题意就是旅馆订房问题，由于牵扯到某一段区间的查找与运算，所以选择了线段树求解，
 10         用free表示此段区间房间是否可用，lmax代表这段区间从左边起最长空闲房间数，rmax表示这段区间
 11         从右边起最长空闲房间数，tmax表示整个区间上的最长连续空闲房间数，查找连续空房间数时，过程如下：
 12             1、如果1~n区间的tmax值都比待查长度len小，就无解，否则有解执行2 
 13             2、假如区间lmax是否大于等于len，直接返回l ，否则执行3 
 14             3、对于每一个区间，如果它的左儿子的tmax值大于等于len，到左儿子里去找。否则执行4 
 15             4、如果左儿子的rmax加上有儿子的lmax大于等于len，直接返回左儿子的右端点减去左儿子的rmax值。
 16             5、否则到右儿子里去找。
 17             PS：对于上述过程，如果满足前面的条件，则不再考虑后面的情况。
 18          更新的时候既进行下压操作，在对某段区间进行处理后（清空房间或占用房间）后，进行更新父节点，
 19          细节看注释！！ 
 20 */
 21 #include<iostream>
 22 #include<cstdio>
 23 const int N=50010;
 24 using namespace std;
 25 struct Node{
 26     int l,r;
 27     int free;
 28     int lmax,rmax,tmax; 
 29 }tree[3*N];
 30 int build(int l,int r,int i){
 31     tree[i].l=l;
 32     tree[i].r=r;
 33     tree[i].lmax=tree[i].rmax=tree[i].tmax=r-l+1; //初始化为区间大小 
 34     tree[i].free=0;
 35     if(l<r){
 36         int mid=(l+r)>>1;
 37         build(l,mid,i<<1);
 38         build(mid+1,r,i<<1|1);
 39     }
 40 }
 41 int query(int i,int len){
 42     if(tree[i].tmax<len) return 0;  //情况1
 43     if(tree[i].lmax>=len) return tree[i].l;  //情况2 
 44     if(tree[i<<1].tmax>=len) return query(i<<1,len); //情况3 
 45     else if(tree[i<<1].rmax+tree[i<<1|1].lmax >= len) //情况4 
 46         return tree[i<<1].r-tree[i<<1].rmax+1;
 47     else return query(i<<1|1,len); //情况5
 48 }
 49 int update(int l,int r,int i,int state){
 50     if(tree[i].l==l&&tree[i].r==r){ //找到此段区间 
 51         tree[i].free=state;
 52         if(state){ //若为1则占用房间 ，否则腾出房间 
 53             tree[i].lmax=tree[i].rmax=tree[i].tmax=0;
 54         }else{
 55             tree[i].lmax=tree[i].rmax=tree[i].tmax=tree[i].r-tree[i].l+1;
 56         }
 57     }else if(tree[i].r > tree[i].l){
 58         if(tree[i].free==1){  //树节点的相应信息向下压，即节点信息细致化 
 59             tree[i<<1].free=tree[i<<1|1].free=1;
 60             tree[i<<1].lmax=tree[i<<1].rmax=tree[i<<1].tmax=0;
 61             tree[i<<1|1].lmax=tree[i<<1|1].rmax=tree[i<<1|1].tmax=0;
 62         }
 63         if(tree[i].free==0){
 64             tree[i<<1].free=tree[i<<1|1].free=0;
 65             tree[i<<1].lmax=tree[i<<1].rmax=tree[i<<1].tmax=tree[i<<1].r-tree[i<<1].l+1;
 66             tree[i<<1|1].lmax=tree[i<<1|1].rmax=tree[i<<1|1].tmax=tree[i<<1|1].r-tree[i<<1|1].l+1;
 67         }
 68         int mid=(tree[i].r+tree[i].l)>>1;
 69         if(mid>=r) update(l,r,i<<1,state);
 70         else if(mid<l) update(l,r,i<<1|1,state);
 71         else{
 72             update(l,mid,i<<1,state);
 73             update(mid+1,r,i<<1|1,state);
 74         }
 75         tree[i].lmax=tree[i<<1].lmax;  //树节点相应信息向上推送，即更新父节点信息 
 76         tree[i].rmax=tree[i<<1|1].rmax;
 77         if(tree[i<<1].free==0) tree[i].lmax+=tree[i<<1|1].lmax;
 78         if(tree[i<<1|1].free==0) tree[i].rmax+=tree[i<<1].rmax;
 79         tree[i].tmax=max(tree[i<<1].tmax,tree[i<<1|1].tmax);  //选取左孩子tmax和右孩子tmax及左右之间结合的最大值 
 80         tree[i].tmax=max(tree[i].tmax,tree[i<<1].rmax+tree[i<<1|1].lmax);
 81         if(tree[i<<1].free==tree[i<<1|1].free)  //更新父节点的使用情况 
 82             tree[i].free=tree[i<<1].free;
 83         else tree[i].free=-1;
 84     }
 85 }
 86 int main()
 87 {
 88     int N,M,s,num,start,flag;
 89     while(~scanf("%d%d",&N,&M)){
 90         build(1,N,1);
 91         while(M--){
 92             scanf("%d",&flag);
 93             if(flag==1){
 94                 scanf("%d",&s);
 95                 start=query(1,s); //start为0说明未找到符合房间 
 96                 printf("%d\n",start);
 97                 if(start) update(start,start+s-1,1,1);  //假如 start不为零，那么就需要占用 
 98             }else{
 99                 scanf("%d%d",&s,&num);
100                 update(s,s+num-1,1,0);
101             }
102         }
103     }
104     return 0;
105 }