1593: [Usaco2008 Feb]Hotel 旅馆
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 391 Solved: 228
[Submit][Status][Discuss]
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
1 3
1 3
1 3
1 3
2 5 5
1 6
Sample Output
4
7
0
5
HINT
Source
题解：萌萌哒线段树，这里面涉及到的问题是求最长0区间，然后也是可以通过区间分治的策略，也就是线段树来搞定；由于涉及到合并区间结果，所以需要存储一个左边的最长空格段和右边的最长空格段，便于维护，然后入住，退房神马的就是直接用tag实现区间赋值即可
（PS：在本机上逗比了N次，发现是tag处理还是有点偏差，还好交上去之后1A了。。。果然我自己还是太弱了OTL）
var
i,j,k,l,m,n:longint;
a,b,c,lk,rk:array[..] of longint;
function max(x,y:longint):longint;inline;
begin
if x>y then max:=x else max:=y;
end;
function min(x,y:longint):longint;inline;
begin
if x<y then min:=x else min:=y;
end;
procedure ext(z,x,y:longint);inline;
begin
if c[z]= then exit;
case c[z] of
:begin
lk[z]:=y-x+;
rk[z]:=y-x+;
b[z]:=y-x+;
a[z]:=;
end;
:begin
lk[z]:=;
rk[z]:=;
b[z]:=;
a[z]:=;
end;
end;
if (x<>y) then
begin
c[z*]:=c[z];
a[z*]:=c[z*];
c[z*+]:=c[z];
a[z*+]:=c[z*+];
if c[z]= then
begin
b[z*]:=;
lk[z*]:=;
rk[z*]:=;
b[z*+]:=;
lk[z*+]:=;
rk[z*+]:=;
end
else
begin
b[z*]:=(x+y) div -x+;
lk[z*]:=b[z*];
rk[z*]:=b[z*];
b[z*+]:=y-(x+y) div ;
lk[z*+]:=b[z*+];
rk[z*+]:=b[z*+];
end;
end;
c[z]:=;
end; procedure built(z,x,y:longint);inline;
begin
if x<>y then
begin
built(z*,x,(x+y) div );
built(z*+,(x+y) div +,y);
end;
lk[z]:=y-x+;
rk[z]:=y-x+;
c[z]:=;
b[z]:=y-x+;
a[z]:=;
end;
procedure refresh(z,x,y:longint);
begin
if x=y then exit;
b[z]:=max(b[z*],b[z*+]);
b[z]:=max(b[z],rk[z*]+lk[z*+]);
if lk[z*]=((y+x) div -x+) then
lk[z]:=lk[z*]+lk[z*+]
else
lk[z]:=lk[z*];
if rk[z*+]=(y-((x+y) div +)+) then
rk[z]:=rk[z*+]+rk[z*]
else
rk[z]:=rk[z*+];
if a[z*]=a[z*+] then a[z]:=a[z*] else a[z]:=;
end;
procedure put(z,x,y,l,r,t:longint);
begin
if l>r then exit;
if (x=l) and (y=r) then
begin
c[z]:=t;
ext(z,x,y);
exit;
end;
ext(z,x,y);
put(z*,x,(x+y) div ,l,min(r,(x+y) div ),t);
put(z*+,(x+y) div +,y,max((x+y) div +,l),r,t);
refresh(z,x,y);
end;
function approach(z,x,y,t:longint):longint;
var a1,a2,a3,a4:longint;
begin
if c[z]= then exit(-);
if c[z]= then
begin
if (y-x+)<t then exit(-) else exit(x);
end;
if lk[z]>=t then exit(x);
if b[z]>=t then
begin
a1:=approach(z*,x,(x+y) div ,t);
if a1<>- then exit(a1);
if (rk[z*]+lk[z*+])>=t then exit((x+y) div -rk[z*]+);
exit(approach(z*+,(x+y) div +,y,t));
end;
if rk[z]>=t then exit(y-rk[z]+);
exit(-);
end;
begin
readln(n,m);
built(,,n);
for i:= to m do
begin
read(j,k);
case j of
:begin
l:=approach(,,n,k);
if l=- then
writeln()
else
begin
put(,,n,l,l+k-,);
writeln(l);
end;
end;
:begin
read(l);
put(,,n,k,k+l-,);
end;
end;
readln;
end;
end.