|
|
Posted on 2012-05-04 20:05 C小加 閱讀(1855) 評(píng)論(0) 編輯 收藏 引用 所屬分類: 解題報(bào)告
區(qū)間合并的線段樹題，也是我的第一個(gè)區(qū)間合并。 題意（轉(zhuǎn)）：Bessie等牛到加拿大的桑德貝去增長(zhǎng)文化修養(yǎng)外帶觀賞蘇必利爾湖的陽光。按照導(dǎo)游的介紹，Bessie選擇了著名的Cumberland大街上的Bullmoose賓館作為居住的地點(diǎn)。 這座巨型賓館在一條超長(zhǎng)走廊上有N（1 ≤ N ≤ 50000）個(gè)排成一排的房間，每個(gè)房間都能欣賞到蘇必利爾湖的好景色?，F(xiàn)在所有的房間都是空的。 現(xiàn)在Bessie等旅客們正在不斷地發(fā)出訂房和退房要求。你需要接受M（1 ≤ M < 50000）條指令： 每條指令的第一個(gè)數(shù)字為1或2。如果是1，后面將有一個(gè)整數(shù)D表示顧客要預(yù)定的房間數(shù)。注意，這些房間必須是連續(xù)的。如果能夠滿足旅客的訂房要求，輸出滿足要求的第一個(gè)房間的編號(hào)（例如，要訂房6間，輸出3表示3, 4, 5, 6, 7, 8是滿足要求的），這樣的編號(hào)必須是可能的編號(hào)里面最靠前的。如果不能滿足要求，輸出0。 如果是2，后面將有兩個(gè)整數(shù)X和D表示顧客要退掉X, X + 1, X + 2, ... , X + D - 1這D間房。對(duì)于這樣的指令什么都不輸出。 分析： 分別用lsum，rsum和msum表示區(qū)間左邊最大連續(xù)房間數(shù)，區(qū)間右邊最大連續(xù)房間數(shù)和區(qū)間最大連續(xù)房間數(shù)。 查詢的時(shí)候，先找左兒子是否足夠，然后如果不夠就找左兒子的右區(qū)間和右兒子的左區(qū)間的和是否足夠，如果兩個(gè)都不夠的話就找右兒子（這個(gè)時(shí)候右兒子就肯定滿足了）。 查詢結(jié)束時(shí)要把這個(gè)區(qū)間的房子更新成已住。 更新的時(shí)候和普通的線段樹節(jié)點(diǎn)更新是一樣的，不同的是在更新完子節(jié)點(diǎn)后，要把子節(jié)點(diǎn)的信息反饋到父節(jié)點(diǎn)中。 在NYOJ中提交TLE，原因居然是宏定義比inline快。
#include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<algorithm> using namespace std; //沒想到我把inline換成宏定義后就AC了，理論上這兩個(gè)一樣的，但是inline的結(jié)果卻是TLE
#define L(r) r<<1 #define R(r) r<<1|1 //inline int MID(int l,int r){return (l+r)>>1;}
//inline int L(int r){return r<<1;}
//inline int R(int r){return r<<1|1;}
const int MAXM=50005; typedef struct{ int lsum,rsum,msum; //分別表示左邊最大房間數(shù)，右邊最大房間數(shù)，整體最大房間數(shù)
int cover; //是否住下
}node; node tree[MAXM<<2]; void pushDown( int root, int m) //向下更新
{ if(tree[root].cover==-1) return; //是否已經(jīng)更新
tree[L(root)].cover=tree[R(root)].cover=tree[root].cover; tree[L(root)].msum=tree[L(root)].lsum=tree[L(root)].rsum=tree[root].cover?0:m-(m>>1); tree[R(root)].msum=tree[R(root)].lsum=tree[R(root)].rsum=tree[root].cover?0:(m>>1); tree[root].cover=-1; } void pushUp( int root, int m) //向上更新
{ tree[root].lsum=tree[L(root)].lsum; tree[root].rsum=tree[R(root)].rsum; if(tree[root].lsum==m-(m>>1) ) tree[root].lsum+=tree[R(root)].lsum; if(tree[root].rsum==(m>>1) ) tree[root].rsum+=tree[L(root)].rsum; tree[root].msum=max(tree[R(root)].lsum+tree[L(root)].rsum,max(tree[L(root)].msum,tree[R(root)].msum) ); } void Create( int l, int r, int root) //建樹過程
{ tree[root].cover=-1; tree[root].lsum=tree[root].rsum=tree[root].msum=r-l+1; if(l==r){ return;} int mid=(l+r)>>1; Create(l,mid,L(root)); Create(mid+1,r,R(root)); } void update( int ll, int rr, int c, int l, int r, int root) //更新
{ if(ll<=l&&r<=rr) //如果找到這個(gè)范圍就直接賦值返回，不向下繼續(xù)更新
{ tree[root].msum=tree[root].lsum=tree[root].rsum=c?0:r-l+1; tree[root].cover=c; return; } pushDown(root,r-l+1); //用到這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的時(shí)候就向下更新
int m=(l+r)>>1; if(ll<=m) update(ll,rr,c,l,m,L(root)); if(m<rr) update(ll,rr,c,m+1,r,R(root)); pushUp(root,r-l+1); //向下更新完后需要把節(jié)點(diǎn)信息反饋給父節(jié)點(diǎn)
} int query( int w, int l, int r, int root) //查詢滿足連續(xù)房間數(shù)量的最左節(jié)點(diǎn)
{ if(l==r) return l; pushDown(root,r-l+1 ); //用到這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的時(shí)候就向下更新
int m=(l+r)>>1; if(tree[L(root)].msum>=w) return query(w,l,m,L(root)); //如果左兒子滿足就詢問左兒子
else if(tree[L(root)].rsum+tree[R(root)].lsum>=w) return m-tree[L(root)].rsum+1; //如果左兒子和右兒子之間的數(shù)量滿足，則范圍左兒子右邊連續(xù)房間第一個(gè)的編號(hào)
return query(w,m+1,r,R(root)); //如果兩者都不滿足則詢問右兒子
} int main() { //freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m; while(~scanf("%d %d",&n,&m)) { Create(1,n,1); int a,num,x,d,p; for( int i=0;i<m;++i) { scanf("%d",&a); if(1==a) { scanf("%d",&num); if(tree[1].msum<num) puts("0"); //如果整個(gè)區(qū)間的最大連續(xù)房間數(shù)量小于預(yù)定的數(shù)量就輸出0
else { p=query(num,1,n,1); //找到最左節(jié)點(diǎn)p
printf("%d\n",p); update(p,p+num-1,1,1,n,1); //把已經(jīng)有人的房間標(biāo)記一下
} } else { scanf("%d %d",&x,&d); update(x,x+d-1,0,1,n,1); //把此范圍的房間標(biāo)記成無人
} } } return 0; }
|