HDU 2795 Billboard：線段樹維護廣告牌最大可用矩形高度

題目大意

一塊 h×w 的廣告牌，依次貼 n 個 1×wᵢ 的廣告。每次貼到當前最高可用行的最左端。求每個廣告貼上後所在行號（1-based），若無法貼上輸出 -1。

線段樹節點信息設計

每個節點維護：區間內最大可用寬度。葉子節點對應一行，初始值為 w。

核心操作

構建

void build(int rt, int l, int r) {
    tree[rt] = w;  // 區間最大可用寬度
    if (l == r) return;
    int mid = (l+r)/2;
    build(rt*2, l, mid);
    build(rt*2+1, mid+1, r);
}

查詢 + 更新（合二為一）

// 返回放置行號，同時更新該行剩餘寬度
int query(int rt, int l, int r, int w) {
    if (l == r) {
        tree[rt] -= w;
        return l;
    }
    int mid = (l+r)/2;
    int ans = (tree[rt*2] >= w) ? query(rt*2, l, mid, w) 
                                 : query(rt*2+1, mid+1, r, w);
    tree[rt] = max(tree[rt*2], tree[rt*2+1]);  // 向上更新
    return ans;
}

完整代碼

#include 
#include 
using namespace std;

const int MAXN = 200000;
int tree[MAXN*4];
int h, w, n;

void build(int rt, int l, int r) {
    tree[rt] = w;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
}

int query(int rt, int l, int r, int x) {
    if (l == r) { tree[rt] -= x; return l; }
    int mid = (l+r)>>1;
    int ans = (tree[rt<<1] >= x) ? query(rt<<1, l, mid, x)
                                  : query(rt<<1|1, mid+1, r, x);
    tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
    return ans;
}

int main() {
    while (scanf("%d%d%d", &h, &w, &n) == 3) {
        if (h > n) h = n;  // 優化：行數超過廣告數無意義
        build(1, 1, h);
        while (n--) {
            int q; scanf("%d", &q);
            if (tree[1] < q) puts("-1");
            else printf("%d\n", query(1, 1, h, q));
        }
    }
    return 0;
}

關鍵優化與技巧

複雜度分析

• 構建：O(h)
• 單次查詢/更新：O(log h)
• 總計：O(h + n log h)，h,n≤200000 時極快
• 空間：O(4h) 整數數組

線段樹模板泛化

此題展示了線段樹「區間最大值 + 查找第一個滿足條件位置」的經典模式。可擴展到：

• 區間最小值查找第一個 ≤ x 的位置
• 區間和查找前綴和 ≥ x 的位置
• 區間 OR/AND 等位運算查找

總結

HDU 2795 是線段樹入門佳作：模型簡單（單點更新、全局最大查詢）、代碼精簡（查詢更新合一）、優化實用（h=n 剪枝）。掌握此題即掌握了線段樹「查找第一個滿足條件位置」的核心套路。