POJ 3667 Hotel：線段樹維護區間最大連續空閒房間

問題描述

酒店有 n 個房間（1..n），支持兩種操作：

1. 入住：查詢是否有連續 x 個空房間，若有輸出最左端位置並標記為已佔用；否則輸出 0。
2. 退房：將區間 [x, x+y-1] 標記為空閒。

n ≤ 50,000，操作數 m ≤ 50,000。

線段樹節點信息

每個節點維護區間 [l, r] 內：

• lsum：從左端點開始的最大連續空閒長度。
• rsum：從右端點開始的最大連續空閒長度。
• msum：區間內任意位置的最大連續空閒長度。
• cover：懶標記，-1 表示無標記，0 表示全空，1 表示全滿。

關鍵操作

PushUp（合併左右子節點）

void pushup(int rt, int len) {
    int lc = rt<<1, rc = rt<<1|1;
    int lLen = len - (len>>1), rLen = len>>1;
    lsum[rt] = lsum[lc];
    rsum[rt] = rsum[rc];
    if (lsum[rt] == lLen) lsum[rt] += lsum[rc]; // 左子區間全空，可合併右子區間左段
    if (rsum[rt] == rLen) rsum[rt] += rsum[lc]; // 右子區間全空，可合併左子區間右段
    msum[rt] = max({msum[lc], msum[rc], rsum[lc] + lsum[rc]}); // 跨中點合併
}

PushDown（下傳懶標記）

void pushdown(int rt, int len) {
    if (cover[rt] != -1) {
        int lc = rt<<1, rc = rt<<1|1;
        int lLen = len - (len>>1), rLen = len>>1;
        cover[lc] = cover[rc] = cover[rt];
        lsum[lc] = rsum[lc] = msum[lc] = cover[rt] ? 0 : lLen;
        lsum[rc] = rsum[rc] = msum[rc] = cover[rt] ? 0 : rLen;
        cover[rt] = -1;
    }
}

查詢最左端可容納 x 的位置

int query(int x, int l, int r, int rt) {
    if (l == r) return l;
    pushdown(rt, r-l+1);
    int mid = (l+r)>>1, lc = rt<<1, rc = rt<<1|1;
    if (msum[lc] >= x) return query(x, l, mid, lc);
    if (rsum[lc] + lsum[rc] >= x) return mid - rsum[lc] + 1;
    return query(x, mid+1, r, rc);
}

完整程式碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50000;
int lsum[MAXN<<2], rsum[MAXN<<2], msum[MAXN<<2], cover[MAXN<<2];

void build(int l, int r, int rt) {
    lsum[rt] = rsum[rt] = msum[rt] = r - l + 1;
    cover[rt] = -1;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
}

void pushdown(int rt, int len) { /* 同上 */ }
void pushup(int rt, int len) { /* 同上 */ }

void update(int L, int R, int val, int l, int r, int rt) {
    if (L <= l && r <= R) {
        lsum[rt] = rsum[rt] = msum[rt] = val ? 0 : r-l+1;
        cover[rt] = val;
        return;
    }
    pushdown(rt, r-l+1);
    int mid = (l+r)>>1;
    if (L <= mid) update(L, R, val, l, mid, rt<<1);
    if (mid < R) update(L, R, val, mid+1, r, rt<<1|1);
    pushup(rt, r-l+1);
}

int query(int x, int l, int r, int rt) { /* 同上 */ }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        build(1, n, 1);
        while (m--) {
            int op; cin >> op;
            if (op == 1) {
                int x; cin >> x;
                if (msum[1] < x) cout << 0 << '\n';
                else {
                    int pos = query(x, 1, n, 1);
                    cout << pos << '\n';
                    update(pos, pos+x-1, 1, 1, n, 1);
                }
            } else {
                int x, y; cin >> x >> y;
                update(x, x+y-1, 0, 1, n, 1);
            }
        }
    }
    return 0;
}

複雜度分析

• 建樹：O(n)
• 單次更新/查詢：O(log n)
• 總時間：O((n+m) log n)
• 空間：O(n)

總結

本題是線段樹維護「區間最大連續子段」的經典模板題。關鍵在於節點信息的定義與 PushUp 邏輯，以及懶標記的正確下傳。查詢時優先走左子樹、再檢查跨中點、最後右子樹，保證找到最左端位置。