HDU 2795 Billboard - 線段樹區間最大值查詢佈告欄廣告投放

struct Node {
    int l, r;
    int maxWidth;  // 區間內最大可用寬度
} tree[MAXN * 4];

核心操作

建樹：初始每行寬度為 w

void build(int l, int r, int idx) {
    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);
    build(mid + 1, r, idx << 1 | 1);
}

查詢並更新：找到最上方可放置的行

int query(int width, int idx) {
    if (tree[idx].l == tree[idx].r) {  // 葉子節點：具體行
        tree[idx].maxWidth -= width;
        return tree[idx].l;  // 返回行號
    }
    // 優先查左子樹（上方行）
    if (tree[idx<<1].maxWidth >= width)
        return query(width, idx << 1);
    else
        return query(width, idx << 1 | 1);
}

完整主程序

#include 
#include 
#include 
using namespace std;

const int MAXN = 200010;
struct Node { int l, r, maxWidth; } tree[MAXN * 4];
int h, w, n;

int main() {
    while (scanf("%d%d%d", &h, &w, &n) == 3) {
        int rows = min(h, n);
        build(1, rows, 1);
        
        for (int i = 0; i < n; ++i) {
            int wi; scanf("%d", &wi);
            if (tree[1].maxWidth < wi) {
                printf("-1\n");
            } else {
                printf("%d\n", query(wi, 1));
            }
        }
    }
    return 0;
}

範例執行

輸入: 3 5 5
      2 4 3 3 3
      
過程:
行1: 放寬度2 → 剩餘3
行2: 放寬度4 → 剩餘1  
行1: 放寬度3 → 剩餘0
行3: 放寬度3 → 剩餘2
行1/2/3均無法放寬度3 → -1

輸出: 1 2 1 3 -1

複雜度分析

關鍵技巧總結

1. 行數壓縮：min(h, n) 避免 10^9 空間爆炸
2. 最大值維護：區間最大剩餘寬度，查詢時優先走左子樹（上方行）
3. 葉子即行號：線段樹葉子節點直接對應行號，無需額外映射
4. 遞歸查詢更新合一：查找到葉子時直接扣減寬度並返回行號