HDU 2795 Billboard：線段樹解決公告牌貼紙佈局問題

題目大意

有一塊高度為 h、寬度為 w 的矩形公告牌（行號 1~h 從上到下）。依次貼上 n 張高度為 1、寬度為 w_i 的矩形公告。貼放規則：

1. 優先選擇最上方（行號最小）可容納的行；
2. 同一行內優選最左側位置；
3. 若無法放置，輸出 -1。

對每張公告，輸出其所在行號。約束：h, w ≤ 10^9, n ≤ 200,000。

核心觀察與線段樹建模

由於 h 極大但實際用到的行數不超過 n（每張公告佔一行），可將有效行數壓縮為 min(h, n)。每行剩餘寬度初始為 w。問題轉化為：

在一個長度為 H = min(h, n) 的數組中，每次查詢區間最大值（剩餘寬度），找到最左側 ≥ w_i 的位置，並將該位置值減去 w_i。

線段樹完美支持「區間最大值查詢 + 單點更新」，時間複雜度 O(log H)。

線段樹節點設計

struct Node {
    int l, r;       // 區間範圍 [l, r]
    int maxWidth;   // 該區間內的最大剩餘寬度
} tree[MAXN * 4];

關鍵操作實現

建樹

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

查詢與更新（合併為一步）

遞歸查找最左滿足條件的葉子節點，並直接更新：

void update(int width, int idx) {
    if (tree[idx].l == tree[idx].r) {
        cout << tree[idx].l << '\n'; // 輸出行號
        tree[idx].maxWidth -= width;
        return;
    }
    // 優先進入左子樹（行號更小）
    if (width <= tree[idx<<1].maxWidth)
        update(width, idx<<1);
    else
        update(width, idx<<1|1);
    // 回溯更新父節點最大值
    tree[idx].maxWidth = max(tree[idx<<1].maxWidth, tree[idx<<1|1].maxWidth);
}

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 5;

struct Node { int l, r, maxWidth; } tree[MAXN * 4];

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

void update(int w, int idx) {
    if (tree[idx].l == tree[idx].r) {
        printf("%d\n", tree[idx].l);
        tree[idx].maxWidth -= w;
        return;
    }
    if (w <= tree[idx<<1].maxWidth) update(w, idx<<1);
    else update(w, idx<<1|1);
    tree[idx].maxWidth = max(tree[idx<<1].maxWidth, tree[idx<<1|1].maxWidth);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int h, w, n;
    while (cin >> h >> w >> n) {
        int H = min(h, n);
        build(1, H, 1, w);
        for (int i = 0, wi; i < n; ++i) {
            cin >> wi;
            if (tree[1].maxWidth >= wi) update(wi, 1);
            else puts("-1");
        }
    }
    return 0;
}

複雜度與優化點

• 時間：O(n log n)，每張公告一次查詢更新。
• 空間：O(n)，線段樹節點數約 4n。
• 關鍵優化：將 h 壓縮至 min(h, n)，避免巨大內存佔用；合併查詢更新減少遞歸開銷。