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