HDU 2795 Billboard：線段樹解決公告張貼問題

問題描述

有一塊高 h、寬 w 的宣傳欄。有 n 條公告，每條高 1、寬 lenᵢ。公告必須貼在「最上面、最靠左」的可用位置。判斷每條公告能否貼上，能則輸出其左上角行號（1-based），否則輸出 -1。

關鍵轉換：倒置思維

原問題是「找最上最左」，等價於將宣傳欄上下翻轉後變為「找最左、且行號最小（即原最上）的可放置行」。此時每行剩餘寬度初始為 w，放入公告後剩餘寬度減少。只需在 h 行中找第一個剩餘寬度 ≥ lenᵢ 的行。

線段樹維護「區間最大剩餘寬度」

• 葉子節點：每行剩餘寬度，初始 w
• 內部節點：存儲子區間的 最大值
• 查詢 len：若根節點最大值 < len 則無解；否則遞歸優先進入左子樹（保證最左），找到葉子後更新剩餘寬度並向上修正最大值

優化：樹的大小只需 min(h, n)

因為最多只會用到 n 行（每條公告佔一行），若 n 只需建 n 行的樹，多餘行永遠不會被使用。

參考代碼（C++）

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

#define repf(i,a,b) for(int i=(a);i<=(b);i++)
#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
typedef long long ll;

const int N = 200010;
const int ROOT = 1;

struct SegNode { ll mx; };
struct SegTree {
    SegNode node[N << 2];
    void update(int pos) { node[pos].mx = max(node[lson(pos)].mx, node[rson(pos)].mx); }
    void build(int l, int r, int pos) {
        if (l == r) { node[pos].mx = w; return; }
        int m = (l + r) >> 1;
        build(l, m, lson(pos));
        build(m+1, r, rson(pos));
        update(pos);
    }
    // 返回能放下 y 的最左行號，或 -1
    int query_modify(int l, int r, int pos, ll y) {
        if (y > node[pos].mx) return -1;
        if (l == r) { node[pos].mx -= y; return l; }
        int m = (l + r) >> 1;
        int res = (y <= node[lson(pos)].mx) ?
            query_modify(l, m, lson(pos), y) :
            query_modify(m+1, r, rson(pos), y);
        update(pos);
        return res;
    }
} seg;

int h, w, n, t;

int main() {
    while (~scanf("%d%d%d", &h, &w, &n)) {
        h = min(h, n); // 關鍵優化
        seg.build(1, h, ROOT);
        repf(i, 1, n) {
            scanf("%d", &t);
            printf("%d\n", seg.query_modify(1, h, ROOT, t));
        }
    }
    return 0;
}

複雜度分析

• 建樹：O(h')，h' = min(h, n)
• 每次查詢+更新：O(log h')
• 總時間：O((h' + n) log h')
• 空間：O(h')

核心技巧總結

1. 幾何翻轉：「最上最左」→「最左且行號最小」
2. 線段樹存最大值：支持「找第一個 ≥ x 的位置」
3. 規模壓縮：樹大小取 min(h, n) 避免 MLE