首页 > 代码库 > (简单) POJ 3667 Hotel，线段树+区间合并。
(简单) POJ 3667 Hotel，线段树+区间合并。
Description
The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).
The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.
Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.
题目大致就是说对一段区间进行两种操作，分别是找到能够容下D的最左边的位置，然后就是更新一段区间为0或1。
很典型的区间覆盖问题，维护最大空房间和前缀最大，后缀最大三个值。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>#define lson L,M,po*2#define rson M+1,R,po*2+1#define lc po*2#define rc po*2+1using namespace std;const int maxn=50005;int msum[maxn*4],lsum[maxn*4],rsum[maxn*4];int COL[maxn*4];void pushDown(int po,int len){ if(COL[po]==1) { COL[lc]=COL[rc]=1; msum[lc]=rsum[lc]=lsum[lc]=0; msum[rc]=rsum[rc]=lsum[rc]=0; COL[po]=-1; } else if(COL[po]==0) { COL[lc]=COL[rc]=0; msum[lc]=rsum[lc]=lsum[lc]=len-(len/2); msum[rc]=rsum[rc]=lsum[rc]=len/2; COL[po]=-1; }}void pushUP(int po,int len){ msum[po]=max(msum[lc],msum[rc]); msum[po]=max(msum[po],rsum[lc]+lsum[rc]); lsum[po]=lsum[lc]; if(lsum[lc]==(len-(len/2))) lsum[po]+=lsum[rc]; rsum[po]=rsum[rc]; if(rsum[rc]==len/2) rsum[po]+=rsum[lc];}void build_tree(int L,int R,int po){ COL[po]=-1; msum[po]=rsum[po]=lsum[po]=R-L+1; if(L==R) return; int M=(L+R)/2; build_tree(lson); build_tree(rson);}void update(int ul,int ur,int ut,int L,int R,int po){ if(ul<=L&&ur>=R) { COL[po]=ut; msum[po]=lsum[po]=rsum[po]=(ut ? 0 : R-L+1); return; } pushDown(po,R-L+1); int M=(L+R)/2; if(ul<=M) update(ul,ur,ut,lson); if(ur>M) update(ul,ur,ut,rson); pushUP(po,R-L+1);}int query(int len,int L,int R,int po){ if(L==R) return L; pushDown(po,R-L+1); int M=(L+R)/2; if(msum[lc]>=len) return query(len,lson); else if(rsum[lc]+lsum[rc]>=len) return M-rsum[lc]+1; else return query(len,rson);}int main(){ int M,N; int a,b,c; while(~scanf("%d %d",&N,&M)) { build_tree(1,N,1); for(int i=0;i<M;++i) { scanf("%d %d",&a,&b); if(a==1) { if(msum[1]<b) printf("%d\n",0); else { c=query(b,1,N,1); update(c,c+b-1,1,1,N,1); printf("%d\n",c); } } else { scanf("%d",&c); update(b,b+c-1,0,1,N,1); } } } return 0;}
(简单) POJ 3667 Hotel，线段树+区间合并。