HDU 3016 Man Down 線段樹 + DP 遊戲優化

問題模型

垂直分佈的木板，每板有高度 h、左右端點 xl, xr、能量值 val（正/負）。角色從最高板（初始能量 100）開始，每次從當前板左/右端點垂直下落，落到最近的下方板。可選擇左/右端點下落。若落地時能量 ≤ 0 則失敗（輸出 -1），否則求最大最終能量。

關鍵難點：快速找到「正下方最近的板」

對每塊板的左右端點，需知下落會落在哪塊板上。暴力 O(N²) 過慢（N≤100,000）。

線段樹離線構建「下落關係」

1. 按高度 h 升序排序所有板（從低向高處理）
2. 線段樹維護 x 軸區間 → 板編號的映射（區間染色/查詢）
3. 處理板 i 時：
   • query(xl) → 落在板 L，記 left[i] = L
   • query(xr) → 落在板 R，記 right[i] = R
   • update(xl, xr, i) —— 將區間染為板 i 的顏色
4. 地面視為虛擬板 0（val=0），初始染色整個 x 軸為 0

DP 計算最大能量

按高度降序（從高向低）處理：

dp[i] = 從板 i 開始能獲得的最大額外能量
dp[left[i]]  = max(dp[left[i]],  dp[i] + val[left[i]]);
dp[right[i]] = max(dp[right[i]], dp[i] + val[right[i]]);

初始 dp[top] = 100。最終答案 dp[0]（地面），若 ≤0 輸出 -1。

線段樹關鍵操作

struct SegNode { int l, r, color; } tree[4*MAXX];

void pushdown(int v) {
    if (tree[v].color != -1) {
        tree[v<<1].color = tree[v<<1|1].color = tree[v].color;
        tree[v].color = -1;
    }
}

void update(int v, int L, int R, int color) {
    if (L <= tree[v].l && tree[v].r <= R) {
        tree[v].color = color; return;
    }
    pushdown(v);
    int mid = (tree[v].l + tree[v].r) >> 1;
    if (R <= mid) update(v<<1, L, R, color);
    else if (L > mid) update(v<<1|1, L, R, color);
    else {
        update(v<<1, L, mid, color);
        update(v<<1|1, mid+1, R, color);
    }
}

int query(int v, int pos) {
    if (tree[v].color != -1) return tree[v].color;
    int mid = (tree[v].l + tree[v].r) >> 1;
    return pos <= mid ? query(v<<1, pos) : query(v<<1|1, pos);
}

複雜度總結

• 排序：O(N log N)
• 線段樹構建下落關係：O(N log X)
• DP：O(N)
• 總體 O(N log N)，滿足 N=100,000