1593: [Usaco2008 Feb]Hotel 旅馆
1593: [Usaco2008 Feb]Hotel 旅馆
1593: [Usaco2008 Feb]Hotel 旅馆
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 391 Solved: 228
Description
奶牛们最近的旅游计划，是到苏必利尔湖畔，享受那里的湖光山色，以及明媚的阳光。作为整个旅游的策划者和负责人，贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的湖面。 贝茜一行，以及其他慕名而来的旅游者，都是一批批地来到旅馆的服务台，希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单：如果存在r满足编号为r..r+D_i-1的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。 旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字X_i、D_i 描述，表示编号为X_i..X_i+D_i-1 (1 <= X_i <= N-D_i+1)房间中的客人全部离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。 而你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要处理M (1 <= M < 50,000)个按输入次序到来的住店或退房的请求。第一个请求到来前，旅店中所有房间都是空闲的。
Input
* 第1行: 2个用空格隔开的整数：N、M
* 第2..M+1行: 第i+1描述了第i个请求，如果它是一个订房请求，则用2个数字 1、D_i描述，数字间用空格隔开；如果它是一个退房请求，用3 个以空格隔开的数字2、X_i、D_i描述
Output
* 第1..??行: 对于每个订房请求，输出1个独占1行的数字：如果请求能被满足 ，输出满足条件的最小的r；如果请求无法被满足，输出0
Sample Input
10 6 1 3 1 3 1 3 1 3 2 5 5 1 6
Sample Output
1 4 7 0 5
HINT
Source
题解：萌萌哒线段树，这里面涉及到的问题是求最长0区间，然后也是可以通过区间分治的策略，也就是线段树来搞定；由于涉及到合并区间结果，所以需要存储一个左边的最长空格段和右边的最长空格段，便于维护，然后入住，退房神马的就是直接用tag实现区间赋值即可
（PS：在本机上逗比了N次，发现是tag处理还是有点偏差，还好交上去之后1A了。。。果然我自己还是太弱了OTL）
1 var
2 i,j,k,l,m,n:longint;
3 a,b,c,lk,rk:array[0..500000] of longint;
4 function max(x,y:longint):longint;inline;
5 begin
6 if x>y then max:=x else max:=y;
7 end;
8 function min(x,y:longint):longint;inline;
9 begin
10 if x<y then min:=x else min:=y;
11 end;
12 procedure ext(z,x,y:longint);inline;
13 begin
14 if c[z]=2 then exit;
15 case c[z] of
16 0:begin
17 lk[z]:=y-x+1;
18 rk[z]:=y-x+1;
19 b[z]:=y-x+1;
20 a[z]:=0;
21 end;
22 1:begin
23 lk[z]:=0;
24 rk[z]:=0;
25 b[z]:=0;
26 a[z]:=1;
27 end;
28 end;
29 if (x<>y) then
30 begin
31 c[z*2]:=c[z];
32 a[z*2]:=c[z*2];
33 c[z*2+1]:=c[z];
34 a[z*2+1]:=c[z*2+1];
35 if c[z]=1 then
36 begin
37 b[z*2]:=0;
38 lk[z*2]:=0;
39 rk[z*2]:=0;
40 b[z*2+1]:=0;
41 lk[z*2+1]:=0;
42 rk[z*2+1]:=0;
43 end
44 else
45 begin
46 b[z*2]:=(x+y) div 2-x+1;
47 lk[z*2]:=b[z*2];
48 rk[z*2]:=b[z*2];
49 b[z*2+1]:=y-(x+y) div 2;
50 lk[z*2+1]:=b[z*2+1];
51 rk[z*2+1]:=b[z*2+1];
52 end;
53 end;
54 c[z]:=2;
55 end;
56
57 procedure built(z,x,y:longint);inline;
58 begin
59 if x<>y then
60 begin
61 built(z*2,x,(x+y) div 2);
62 built(z*2+1,(x+y) div 2+1,y);
63 end;
64 lk[z]:=y-x+1;
65 rk[z]:=y-x+1;
66 c[z]:=2;
67 b[z]:=y-x+1;
68 a[z]:=0;
69 end;
70 procedure refresh(z,x,y:longint);
71 begin
72 if x=y then exit;
73 b[z]:=max(b[z*2],b[z*2+1]);
74 b[z]:=max(b[z],rk[z*2]+lk[z*2+1]);
75 if lk[z*2]=((y+x) div 2-x+1) then
76 lk[z]:=lk[z*2]+lk[z*2+1]
77 else
78 lk[z]:=lk[z*2];
79 if rk[z*2+1]=(y-((x+y) div 2+1)+1) then
80 rk[z]:=rk[z*2+1]+rk[z*2]
81 else
82 rk[z]:=rk[z*2+1];
83 if a[z*2]=a[z*2+1] then a[z]:=a[z*2] else a[z]:=2;
84 end;
85 procedure put(z,x,y,l,r,t:longint);
86 begin
87 if l>r then exit;
88 if (x=l) and (y=r) then
89 begin
90 c[z]:=t;
91 ext(z,x,y);
92 exit;
93 end;
94 ext(z,x,y);
95 put(z*2,x,(x+y) div 2,l,min(r,(x+y) div 2),t);
96 put(z*2+1,(x+y) div 2+1,y,max((x+y) div 2+1,l),r,t);
97 refresh(z,x,y);
98 end;
99 function approach(z,x,y,t:longint):longint;
100 var a1,a2,a3,a4:longint;
101 begin
102 if c[z]=1 then exit(-1);
103 if c[z]=0 then
104 begin
105 if (y-x+1)<t then exit(-1) else exit(x);
106 end;
107 if lk[z]>=t then exit(x);
108 if b[z]>=t then
109 begin
110 a1:=approach(z*2,x,(x+y) div 2,t);
111 if a1<>-1 then exit(a1);
112 if (rk[z*2]+lk[z*2+1])>=t then exit((x+y) div 2-rk[z*2]+1);
113 exit(approach(z*2+1,(x+y) div 2+1,y,t));
114 end;
115 if rk[z]>=t then exit(y-rk[z]+1);
116 exit(-1);
117 end;
118 begin
119 readln(n,m);
120 built(1,1,n);
121 for i:=1 to m do
122 begin
123 read(j,k);
124 case j of
125 1:begin
126 l:=approach(1,1,n,k);
127 if l=-1 then
128 writeln(0)
129 else
130 begin
131 put(1,1,n,l,l+k-1,1);
132 writeln(l);
133 end;
134 end;
135 2:begin
136 read(l);
137 put(1,1,n,k,k+l-1,0);
138 end;
139 end;
140 readln;
141 end;
142 end.