笛卡尔树

BB

水文中的大水文 QvQ

 

Introduction

 

Largest Rectangle in a Histogram - HDU 1506

Description
求最大子矩形面积
Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

Solution
根据笛卡尔树性质，若按小顶堆建树，矩形面积 = 子树大小 * 权值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)100000 + 15;

int ch[N][2];
int stk[N], val[N], sz[N];
int pstk;

inline int build(int n) {
    pstk = 0;
    stk[++pstk] = 0;
    for(int i = 1; i <= n; i++) {
        ch[i][0] = ch[i][1] = 0;
        while(pstk) {
            if(val[stk[pstk]] <= val[i]) {
                ch[stk[pstk]][1] = i;
                break;
            } else {
                ch[stk[pstk]][1] = ch[i][0];
                ch[i][0] = stk[pstk--];
            }
        }
        stk[++pstk] = i;
    }
    return ch[0][1];
}

inline ll dfs(int u) {
    if(!u) {
        return 0;
    }
    ll ans = 0;
    sz[u] = 1;
    for(int j = 0; j < 2; j++) {
        ans = max(ans, dfs(ch[u][j]));
        sz[u] += sz[ch[u][j]];
    }
    ans = max(ans, 1LL * sz[u] * val[u]);
    return ans;
}

int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &val[i]);
        }
        int rt = build(n);
        ll ans = dfs(rt);
        printf("%lld\n", ans);
    }
    return 0;
}