題目鏈接:poj3667
/*poj 3667 Hotel 線段樹區間合並 題意: 操作1:詢問是否有連續x間房間可以住,輸出最左端的房間位置 操作2:顧客退房,將房間清空,表示沒有人住 思路: 利用線段樹建立模型,維護最大連續區間長度,其中區間長度就是對應的房間數目, 並且對應區間中最左邊的端點就是ans,同時因為需要求出連續區間的最大長度, 因此每次PushUp時都將左右區間合並,lsum維護左區間的最大長度,rsum維護右區間的最大長度, sum維護區間1…N中的最大連續區間長度,cover標志對應區間是否為空(沒有住客) */ #include#include #include using namespace std; #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 const int N = 150000; int cover[N<<2]; int llen[N<<2],rlen[N<<2],mlen[N<<2]; void build(int l, int r, int rt) { llen[rt] = rlen[rt] = mlen[rt] = r - l + 1; cover[rt] = -1; if(l == r) return; int m = (l + r) >> 1; build(lson); build(rson); } void pushdown(int rt, int m)//更新子節點 { if(cover[rt] != -1) { llen[rt<<1] = rlen[rt<<1] = mlen[rt<<1] = cover[rt] ? 0 : m - (m>>1); llen[rt<<1|1] = rlen[rt<<1|1] = mlen[rt<<1|1] = cover[rt] ? 0 : (m>>1); cover[rt<<1] = cover[rt<<1|1] = cover[rt]; cover[rt] = -1; } } void pushup(int rt, int m)//更新父節點 { llen[rt] = llen[rt<<1]; rlen[rt] = rlen[rt<<1|1]; if(llen[rt] == m - (m>>1)) llen[rt] += llen[rt<<1|1]; if(rlen[rt] == (m>>1)) rlen[rt] += rlen[rt<<1]; mlen[rt] = max(llen[rt<<1|1] + rlen[rt<<1], max(mlen[rt<<1], mlen[rt<<1|1])); } void update(int L, int R, int c, int l, int r, int rt) { if(L <= l && r <= R) { llen[rt] = rlen[rt] = mlen[rt] = c?0:r-l+1; cover[rt] = c; return ; } pushdown(rt, r-l+1); int m = (l + r) >> 1; if(L <= m) update(L, R, c, lson); if(m < R) update(L, R, c, rson); pushup(rt, r-l+1); } int query(int num, int l, int r, int rt) { if(l == r) return l; pushdown(rt, r-l+1); int m = (l+r) >> 1; if(mlen[rt<<1] >= num) // 左連續區間長度 return query(num, lson); else if(rlen[rt<<1] + llen[rt<<1|1] >= num) // 左區間右半部分與右區間左半部分長度 return m - rlen[rt<<1] + 1; return query(num, rson); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { build(1, n ,1); while(m--) { int op,x,y; scanf("%d",&op); if(op == 1) { scanf("%d",&x); if(mlen[1] < x) puts("0"); else { int ans = query(x, 1, n, 1); printf("%d\n",ans); update(ans, ans + x - 1, 1, 1, n, 1); } } if(op == 2) { scanf("%d%d",&x,&y); update(x, x+y-1, 0, 1, n, 1); } } } return 0; }