Author: lllyouo
Date: 20250921
tag: 单调栈、笛卡尔树
link: https://www.acwing.com/problem/content/133

问题描述

link

分析

略

参考代码

单调栈解法：

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

const int N = 1e6 + 10;
int n, ans, h[N], st[N], top;

signed main() {
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++) cin >> h[i];
        h[0] = h[n + 1] = 0; // 哨兵

        top = 0, ans = 0;
        st[++top] = h[0]; // 哨兵
        for (int i = 1; i <= n + 1; i++) {
            while (h[st[top]] > h[i]) {
                int height = h[st[top]];
                top--;
                int width = i - st[top] - 1;
                ans = max(ans, width * height);

                cout << i << " " << width * height << endl;
            }
            st[++top] = i;
        }
        cout << ans << endl;
    }

    return 0;
}

笛卡尔树解法：

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

const int N = 1e7 + 10;
int n, ans, v[N], ls[N], rs[N], st[N], top;

int build() {
    for (int i = 1; i <= n; i++) {
        int k = top;
        while (k > 0 && v[st[k]] > v[i]) k--;
        if (k) rs[st[k]] = i;
        if (k < top) ls[i] = st[k + 1];
        st[++k] = i;
        top = k;
    }

    return st[1];
}

int dfs(int x) {
    if (!x) return 0;

    int sz = dfs(ls[x]);
    sz += dfs(rs[x]);
    ls[x] = rs[x] = 0;
    ans = max(ans, (sz + 1) * v[x]);

    return sz + 1;
}

signed main() {
    while (cin >> n, n) {
        for (int i = 1; i <= n; i++) scanf("%lld", &v[i]);

        top = 0, ans = 0;
        int root = build();

        dfs(root);
        cout << ans << endl;
    }

    return 0;
}