POJ3667 HOTEL

【题目大意】

     有一个旅馆，有N个房间排成一排，现在有两种操作，第一是有X个顾客要入住连续的X个房间，要求输出最小的左端点的位置，不能满足就输出0，第二是将以l开始，长度为X的连续房间清空。

【输入文件】

     第一行两个数N，M，表示房间数和操作数

     接下来M行，每行有两种情况：

     1 X 表示操作1

     2 l X 表示操作2

【输出文件】

     对于每一个1操作，输出答案。

【输入样例】

10 6

1 3

1 3

1 3

1 3

2 5 5

1 6

【输出样例】

1

4

7

0

5

【题目分析】

     方案一：线段树

     首先最经典的是线段树的做法，在每个节点上新加3个域Z，Y，S，Z表示区间左边连续的空房个数，Y表示区间有边连续的空房个数，S表示区间上最大的一段空房的长度。

     那么：

      A[i].z:=a[a[i].l].z（左区间不都为空时）

            A[a[i].l].len+a[a[i].r].z（左区间为空时）

      A[i].y类似。

      A[i].s:=max(a[a[i].l].s,a[a[i].r].s,a[a[i].l].y+a[a[i].r].z)

     插入和删除线段时要用到lazy操作

     查询时：

        1、如果1~n区间的S值都比X小，就无解，否则有解。

        2、对于每一个区间，如果它的左儿子的S值大于等于X，到左儿子里去找。

        3、如果左儿子的Y加上有儿子的Z大于等于X，直接返回左儿子的右端点减去左儿子的Y值。

        4、否则到右儿子里去找。

        5、如果满足2，则不再考虑3，4；同样，满足3就不再考虑4。

     

1 program poj3667;  2 type tree=record  3       a,b,l,r,z,y,s,bj:longint;  4      end;  5 var a:array[0..100000]of tree;  6     i,j,m,n,k,x,tot,ans,p,l,r:longint;  7 procedure make(l,r:longint);  8 var mid,now:longint;  9 begin 10     inc(tot); 11     a[tot].a:=l; 12     a[tot].b:=r; 13     a[tot].z:=r-l; 14     a[tot].y:=r-l; 15     a[tot].s:=r-l; 16     mid:=(l+r)shr 1; 17     if l
       
        b then exit(a) 29     else exit(b); 30 end; 31 procedure calc(i:longint); 32 begin 33     if a[a[i].l].z=a[a[i].l].b-a[a[i].l].a then a[i].z:=a[a[i].l].z+a[a[i].r].z 34     else a[i].z:=a[a[i].l].z; 35     if a[a[i].r].y=a[a[i].r].b-a[a[i].r].a then a[i].y:=a[a[i].r].y+a[a[i].l].y 36     else a[i].y:=a[a[i].r].y; 37     a[i].s:=max(max(a[a[i].l].s,a[a[i].r].s),a[a[i].l].y+a[a[i].r].z); 38 end; 39 procedure clean(i:longint); 40 begin 41     a[a[i].l].bj:=a[i].bj; 42     a[a[i].r].bj:=a[i].bj; 43     if a[i].bj=1 then 44     begin 45         a[a[i].l].z:=0; 46         a[a[i].r].z:=0; 47         a[a[i].l].y:=0; 48         a[a[i].r].y:=0; 49         a[a[i].l].s:=0; 50         a[a[i].r].s:=0; 51     end 52     else 53     begin 54         a[a[i].l].z:=a[a[i].l].b-a[a[i].l].a; 55         a[a[i].r].z:=a[a[i].r].b-a[a[i].r].a; 56         a[a[i].l].y:=a[a[i].l].b-a[a[i].l].a; 57         a[a[i].r].y:=a[a[i].r].b-a[a[i].r].a; 58         a[a[i].l].s:=a[a[i].l].b-a[a[i].l].a; 59         a[a[i].r].s:=a[a[i].r].b-a[a[i].r].a; 60     end; 61     a[i].bj:=0; 62 end; 63 procedure insert(i,l,r:longint); 64 var mid:longint; 65 begin 66     if (l<=a[i].a)and(a[i].b<=r) then 67     begin 68         a[i].z:=0; 69         a[i].y:=0; 70         a[i].s:=0; 71         a[i].bj:=1; 72         exit; 73     end; 74     mid:=(a[i].a+a[i].b)shr 1; 75     if a[i].bj<>0 then clean(i); 76     if l
        
         0 then clean(i); 93     if l
         
          0 then clean(i);102     if a[a[i].l].s>=x then exit(get(a[i].l,x));103     if a[a[i].l].y+a[a[i].r].z>=x then exit(a[a[i].l].b-a[a[i].l].y+1);104     exit(get(a[i].r,x));105 end;106 begin107     readln(n,m);108     make(0,n);109     for i:=1 to m do110     begin111         read(k);112         if k=1 then113         begin114             readln(x);115             l:=get(1,x);116             writeln(l);117             r:=l+x-1;118             if l<>0 then insert(1,l-1,r);119         end120         else121         begin122             readln(l,r);123             r:=l+r-1;124             delete(1,l-1,r);125         end;126     end;127 end.
         
        
       

 

      方案二：链表

      首先表示这个方法不是自己想的，是小银月亮童鞋想出来的。

      搞一个链表，链表的每个元素是一段连续空房的区间，查询时找到第一个长度足够的区间，然后更新这个区间的左右端点或直接将该区间删除，增加空房时就将给出的区间与原有区间合并。

      这个方法的理论复杂度是N^2的，对于随机数据常数较小，但是还是能被一些数据能卡住。

      事实证明，这个方法对付POJ的数据绰绰有余，上面的线段树方法454ms，链表的做法344ms

 

1 program poj3667_2; 2 type lian=record 3       l,r,last,next:longint; 4      end; 5 var a:array[0..100000]of lian; 6     i,j,m,n,k,x,l,r,tot,tp:longint; 7 function max(a,b:longint):longint; 8 begin 9     if a>b then exit(a)10     else exit(b);11 end;12 function min(a,b:longint):longint;13 begin14     if a-1)and(a[i].r-a[i].l+1