HDU 2795：Billboard（廣告牌，線段樹）

一、題目大意

廣告牌高度 h，寬度 w。初始每行剩餘寬度 w。每次來一個寬度 a 的廣告，找最上方（最小行號）剩餘 ≥ a 的行，放置並減少剩餘寬度。輸出行號，找不到輸出 -1。h 可大於廣告數 n，實際只需建 min(h,n) 行。

二、解題思路：線段樹維護區間最大值

線段樹節點存儲區間最大剩餘寬度。查找最左 ≥ a 的位置：遞歸優先進入左子樹，若左子樹最大值 ≥ a 則去左邊，否則去右邊。找到葉子節點後更新值（減 a），回溯更新祖先最大值。利用線段樹自頂向下、從左到右的遞歸特性，天然找到最左符合位置。

三、代碼實現（C++）

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

const int MAXN = 200010;
int h, w, n;
int maxv[MAXN << 2];

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

int query(int a, int l, int r, int o) {
    if (l == r) { maxv[o] -= a; return l; }
    int mid = (l+r)>>1;
    int ans;
    if (maxv[o<<1] >= a) ans = query(a, l, mid, o<<1);
    else ans = query(a, mid+1, r, o<<1|1);
    maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
    return ans;
}

int main() {
    while (~scanf("%d%d%d", &h, &w, &n)) {
        if (h > n) h = n;
        build(1, h, 1);
        for (int i=0; i