旅馆(hotel)
【问题描述】
OIER们最近的旅游计划，是到长春净月潭，享受那里的湖光山色，以及明媚的阳光。你作为整个旅游的策划者和负责人，选择在潭边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50000)间客房，它们在同一层楼中顺次一字排开，在任何一个房间里，只需要拉开窗帘，就能见到波光粼粼的潭面。
所有的旅游者，都是一批批地来到旅馆的服务台，希望能订到Di (1 <= Di <= N)间连续的房间。服务台的接待工作也很简单：如果存在r满足编号为r..r+Di-1的房间均空着，他就将这一批顾客安排到这些房间入住；如果没有满足条件的r，他会道歉说没有足够的空房间，请顾客们另找一家宾馆。如果有多个满足条件的r，服务员会选择其中最小的一个。
旅馆中的退房服务也是批量进行的。每一个退房请求由2个数字Xi、Di描述，表示编号为Xi..Xi+Di-1 (1 <= Xi <= N-Di+1)房间中的客人全部离开。退房前，请求退掉的房间中的一些，甚至是所有，可能本来就无人入住。
你的工作，就是写一个程序，帮服务员为旅客安排房间。你的程序一共需要处理M (1 <= M <=50000)个按输入次序到来的住店或退房的请求。第一个请求到来前，旅店中所有房间都是空闲的。
【输入格式】
从文件hotel.in中输入数据。
第1行: 2个用空格隔开的整数：N、M
第2..M+1行: 第i+1描述了第i个请求，如果它是一个订房请求，则用2个数字1、Di描述，数字间用空格隔开；如果它是一个退房请求，用3个以空格隔开的数字2、Xi、Di描述。
【输出格式】
输出到文件hotel.out中。
第1..??行: 对于每个订房请求，输出1个独占1行的数字：如果请求能被满足，输出满足条件的最小的r；如果请求无法被满足，输出0。
【样例输入】
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
【样例输出】
1
4
7
0
5
【数据规模与约定】
对于20%的数据， 1<=N<=100,1<=M<=200
对于100%的数据，1 <= N <= 50000 ，1 <= M <= 50000，数据有梯度。
一个很普通的线段树，单纯的不行（然而自己pushdown写错，还是图样）；
维护一下每个区间能住的最大前缀，能住的最大后缀，以及能住的最大连续长度；
回溯的时候最大连续长度从左子连续最大，右子连续最大，左子后缀与右子前缀之和中取最大；
几乎是裸线段树，复杂度就是一个O（n logn）的建树（预处理）；
以及O（m logn）的查询修改操作；
以下代码
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define lson rt*2,l,(l+r)/2 6 #define rson rt*2+1,(l+r)/2+1,r 7 using namespace std; 8 struct node{int ll,rl,le,mark;}tree[400010]; 9 void pushup(int rt,int l,int r) 10 { 11 int mid=(l+r)/2; 12 tree[rt].ll=tree[rt*2].ll; 13 tree[rt].rl=tree[rt*2+1].rl; 14 if(tree[rt].ll==(mid-l+1)) tree[rt].ll+=tree[rt*2+1].ll; 15 if(tree[rt].rl==(r-mid)) tree[rt].rl+=tree[rt*2].rl; 16 tree[rt].le=max(tree[rt*2].rl+tree[rt*2+1].ll,max(tree[rt*2].le,tree[rt*2+1].le)); 17 } 18 void Supdate(int rt,int l,int r,int x) 19 { 20 tree[rt].mark=x; 21 if(x==0) 22 {tree[rt].ll=0; tree[rt].rl=0; tree[rt].le=0;} 23 else 24 {tree[rt].ll=r-l+1; tree[rt].rl=r-l+1; tree[rt].le=r-l+1;} 25 } 26 void pushdown(int rt,int l,int r) 27 { 28 if(tree[rt].mark==-1) return; 29 Supdate(lson,tree[rt].mark); 30 Supdate(rson,tree[rt].mark); 31 tree[rt].mark=-1; 32 } 33 void buildtree(int rt,int l,int r) 34 { 35 tree[rt].mark=-1; 36 if(l==r) 37 { 38 tree[rt].ll=1; 39 tree[rt].rl=1; 40 tree[rt].le=1; 41 return; 42 } 43 buildtree(lson); 44 buildtree(rson); 45 pushup(rt,l,r); 46 } 47 void update(int rt,int l,int r,int f,int t,int x) 48 { 49 int mid=(l+r)/2; 50 if(l==f && r==t) 51 { 52 Supdate(rt,l,r,x); 53 return; 54 } 55 pushdown(rt,l,r); 56 if(t<=mid) update(lson,f,t,x); 57 else if(f>mid) update(rson,f,t,x); 58 else 59 {update(lson,f,mid,x); update(rson,mid+1,t,x);} 60 pushup(rt,l,r); 61 } 62 int query(int rt,int l,int r,int x) 63 { 64 pushdown(rt,l,r); 65 if(tree[rt*2].le>=x) return query(lson,x); 66 else if(tree[rt*2].rl+tree[rt*2+1].ll>=x) return (l+r)/2-tree[rt*2].rl+1; 67 else return query(rson,x); 68 } 69 int main() 70 { 71 // freopen("hotel.in","r",stdin); 72 // freopen("hotel.out","w",stdout); 73 int n,m,i,lk,x,y; 74 scanf("%d%d",&n,&m); 75 buildtree(1,1,n); 76 for(i=1;i<=m;++i) 77 { 78 scanf("%d",&lk); 79 if(lk==1) 80 { 81 scanf("%d",&x); 82 if(tree[1].le<x) 83 {printf("0 "); continue;} 84 y=query(1,1,n,x); 85 printf("%d ",y); 86 update(1,1,n,y,y+x-1,0); 87 } 88 if(lk==2) 89 { 90 scanf("%d%d",&x,&y); 91 y=x+y-1; 92 update(1,1,n,x,y,1); 93 } 94 } 95 }