山脉滑翔(Mountain Range) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct SegTree {
    int n;
    vector<int> mx;
    SegTree(int n) : n(n), mx(4 * n + 5, 0) {}
    void update(int u, int l, int r, int p, int v) {
        if (l == r) {
            mx[u] = max(mx[u], v);
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(u << 1, l, mid, p, v);
        else update(u << 1 | 1, mid + 1, r, p, v);
        mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
    }
    int query(int u, int l, int r, int ql, int qr) const {
        if (ql > qr) return 0;
        if (ql <= l && r <= qr) return mx[u];
        int mid = (l + r) >> 1;
        int res = 0;
        if (ql <= mid) res = max(res, query(u << 1, l, mid, ql, qr));
        if (qr > mid) res = max(res, query(u << 1 | 1, mid + 1, r, ql, qr));
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    vector<int> L(n + 1, 0), R(n + 1, n + 1), stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && h[stk.back()] < h[i]) stk.pop_back();
        L[i] = stk.empty() ? 0 : stk.back();
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && h[stk.back()] < h[i]) stk.pop_back();
        R[i] = stk.empty() ? (n + 1) : stk.back();
        stk.push_back(i);
    }
    vector<pair<int, int>> ord(n);
    for (int i = 1; i <= n; ++i) ord[i - 1] = {h[i], i};
    sort(ord.begin(), ord.end());
    SegTree seg(n);
    vector<int> dp(n + 1, 1);
    int ans = 0;
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && ord[j].first == ord[i].first) ++j;
        for (int k = i; k < j; ++k) {
            int idx = ord[k].second;
            dp[idx] = 1 + seg.query(1, 1, n, L[idx] + 1, R[idx] - 1);
            ans = max(ans, dp[idx]);
        }
        for (int k = i; k < j; ++k) {
            int idx = ord[k].second;
            seg.update(1, 1, n, idx, dp[idx]);
        }
        i = j;
    }
    cout << ans << "\n";
    return 0;
}