POJ 3667 Hotel：線段樹區間合並管理房間入住

操作

• 1 D：入住 D 間連續房，分配最小起始號，不可則輸出 0
• 2 X D：退房 [X, X+D-1]

線段樹節點信息

lsum：前綴連續空房數
rsum：後綴連續空房數
msum：區間最大連續空房數
cover：-1=無標記，0=全滿，1=全空

PushUp 合並邏輯

void PushUp(int rt, int m) {
    lsum[rt] = lsum[lc];
    rsum[rt] = rsum[rc];
    if (lsum[rt] == m - (m>>1)) lsum[rt] += lsum[rc];
    if (rsum[rt] == (m>>1)) rsum[rt] += rsum[lc];
    msum[rt] = max({msum[lc], msum[rc], rsum[lc] + lsum[rc]});
}

查詢最左可行位置

int query(int w, int l, int r, int rt) {
    if (l == r) return l;
    PushDown(rt, r-l+1);
    int m = (l+r)>>1;
    if (msum[lc] >= w) return query(w, lson);
    if (rsum[lc] + lsum[rc] >= w) return m - rsum[lc] + 1;
    return query(w, rson);
}

入住時先查詢再更新區間 cover=0；退房更新 cover=1。初始全空 msum=lsum=rsum=len。