HDU 2795 Billboard：線段樹區間最大值查詢與更新實戰

題目大意

一塊 h × w 的廣告牌，依序貼上 n 張寬 wi、高 1 的廣告。每張廣告總是貼在最左上角可行位置（即：最上方的行中，最左邊能放下的位置）。若無法放置輸出 -1，否則輸出該廣告所在的行號（1-based）。h, w ≤ 10^5, n ≤ 200000。

線段樹建模

• 每個葉節點代表一行，儲存該行剩餘寬度（初始為 w）。
• 內部節點儲存子區間最大剩餘寬度。
• 查詢：從根節點遞歸，優先走左子樹（較上方），找到第一個剩餘 ≥ wi 的葉節點，更新該葉與祖先節點的最大值。
• 若根節點最大值 < wi，直接輸出 -1。

優化技巧

1. h > n 時，多餘行永遠用不到，直接令 h = n，節省空間與時間。
2. 查詢與更新合併在同一遞歸函式中，避免二次遍歷。

完整代碼

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 222222;
int tree[MAXN << 2];
int h, w, n;

void push_up(int rt) {
    tree[rt] = max(tree[rt<<1], tree[rt<<1|1]);
}

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);
    push_up(rt);
    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)，完全滿足限制。

學習重點

1. 線段樹維護「區間最大值」支援「首次滿足條件查詢」。
2. 查詢時優先左子樹 = 優先上方行。
3. 更新邏輯融入查詢返回路徑，push_up 維護祖先資訊。
4. 實際行數取 min(h, n) 是常見優化手法。