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

問題描述

賓館有 n 個房間，支持兩種操作：
1 d：查詢最左邊的連續 d 個空房間的起始位置
2 x d：將從 x 開始的連續 d 個房間標記為空閒

線段樹節點信息

每個節點維護區間 [l, r] 的三個值：

• lm：從左端點開始的最大連續空房間數
• rm：從右端點開始的最大連續空房間數
• mx：區間內最大連續空房間數

PushUp 合併邏輯

void pushup(int rt, int l, int r) {
    int m = (l + r) >> 1;
    int lc = rt << 1, rc = rt << 1 | 1;
    
    node[rt].mx = max({node[lc].mx, node[rc].mx, node[lc].rm + node[rc].lm});
    
    node[rt].lm = node[lc].lm;
    if (node[lc].lm == m - l + 1) // 左子區間全空
        node[rt].lm += node[rc].lm;
    
    node[rt].rm = node[rc].rm;
    if (node[rc].rm == r - m) // 右子區間全空
        node[rt].rm += node[lc].rm;
}

區間更新與查詢

• 更新：標記區間為佔用(0)或空閒(長度)，懶標記下傳
• 查詢：遞歸查找最左滿足長度 ≥ d 的位置
  　　優先查左子樹 → 再查跨中間區間 → 最後查右子樹

查詢函數實現

int query(int d, int l, int r, int rt) {
    if (l == r) return l;
    pushdown(rt, l, r);
    int m = (l + r) >> 1;
    if (node[rt<<1].mx >= d) return query(d, l, m, rt<<1);
    if (node[rt<<1].rm + node[rt<<1|1].lm >= d) return m - node[rt<<1].rm + 1;
    return query(d, m+1, r, rt<<1|1);
}

複雜度

單次操作 O(log n)，總時間 O((n+m) log n)，空間 O(n)。