您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LA 6531 Go up the Ultras：單調棧 + RMQ 求山峰突出度

編輯：關於C++

LA 6531 Go up the Ultras 詳解

題目：給定 N (≤10⁵) 座山峰，每峰有高度 h[i]。對每峰 i，定義其「突出度」 d[i]：對於所有嚴格高於 h[i] 的山峰 j，考慮從 i 到 j 的路徑上最低點的高度（山口高度），取所有這些山口高度的最大值 max_saddle，則 d[i] = h[i] - max_saddle。若不存在更高峰，d[i] = h[i]。問有多少峰的 d[i] ≥ 150000，輸出其下標（1-based）。

核心洞察：單調棧找「左/右第一個更高峰」

對於峰 i，所有更高峰分布在左右兩側。關鍵觀察：
左側最近的更高峰 L[i] 與 右側最近的更高峰 R[i] 之間的區間 [L[i], R[i]] 內，最低點即為通往所有更高峰必經的最高山口。
原因：若有一更高峰在 L[i] 左側，則去那峰必經 L[i]，山口不超過 [L[i], i] 最低點；同理右側。因此：

max_saddle = max( min_height(L[i], i), min_height(i, R[i]) )

其中 min_height(a,b) 為區間 [a,b] 的最小高度。

算法流程

單調棧求 L[i], R[i]：
- 左到右掃描，維護單調遞減棧（存下標）。當 h[i] > h[st.top()]，彈出 top，其 R[top] = i。最後 i 入棧。剩餘元素 R = i（或 n）。
- 右到左掃描，同理求 L[i]。
RMQ 預處理區間最小值：
稀疏表 st[i][k] 存 [i, i+2ᵏ-1] 最小值。查詢 O(1)。
min(l,r) = min(st[l][k], st[r-2ᵏ+1][k])，k = floor(log2(r-l+1))。

計算 d[i]：

if L[i]==i && R[i]==i: d = h[i]          // 無更高峰
else {
    double m1 = (L[i]!=i) ? query_min(L[i], i) : INF;
    double m2 = (R[i]!=i) ? query_min(i, R[i]) : INF;
    d = h[i] - max(m1, m2);
}

統計 d ≥ 150000 的峰，輸出下標。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100050;
const int LOG = 18; // 2^17 > 1e5
int h[MAXN], L[MAXN], R[MAXN];
int st_min[MAXN][LOG];
int lg2[MAXN];

int query_min(int l, int r) {
    int k = lg2[r - l + 1];
    return min(st_min[l][k], st_min[r - (1<>1] + 1;

    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> h[i];
            st_min[i][0] = h[i];
            L[i] = R[i] = i;
        }
        // RMQ 建表
        for (int k = 1; k < LOG; ++k)
            for (int i = 1; i + (1< stk;
        for (int i = 1; i <= n; ++i) {
            while (!stk.empty() && h[stk.top()] < h[i]) {
                R[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
        while (!stk.empty()) stk.pop();
        // 求 L[i] (左側第一個更高)
        for (int i = n; i >= 1; --i) {
            while (!stk.empty() && h[stk.top()] < h[i]) {
                L[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }

        vector ans;
        for (int i = 1; i <= n; ++i) {
            int saddle = 0;
            if (L[i] != i) saddle = max(saddle, query_min(L[i], i));
            if (R[i] != i) saddle = max(saddle, query_min(i, R[i]));
            int d = h[i] - saddle;
            if (d >= 150000) ans.push_back(i);
        }
        for (int i = 0; i < ans.size(); ++i) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}