poj 2559 & hdu 1506 Largest Rectangle in a Histogram 笛卡尔树_问题即为选k个不相交的矩形使得面积和最大 笛卡尔树

题目：

http://poj.org/problem?id=2559

题意：

有n个高度不等的矩形，问这些矩形的所能组成的新矩形的最大面积

思路：

单调栈，dp都可以做，笛卡尔树也可以做。按出现的次序做val，矩形高度做pri，然后O(n)建小顶堆的笛卡尔树，可以惊奇的发现，对于树上的每个节点，以它作为高的新矩形的面积就是以它为根的子树大小乘以它的高，为什么会这样？仔细想想构建小顶堆的笛卡尔树过程，就明白了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N = 100000 + 10, INF = 0x3f3f3f3f;
struct node
{
    int val, pri, fat, son[2];
    friend bool operator< (node a, node b)
    {
        return a.val < b.val;
    }
    void init(int _val, int _pri, int _fat)
    {
        val = _val, pri = _pri, fat = _fat;
        son[0] = son[1] = 0;
    }
}tr[N];
int root;
int top, stk[N];
ll ans;
//int cartesian_build(int n)
//{
//    top = 0;
//    for(int i = 1; i <= n; i++)
//    {
//        int k = top;
//        while(k > 0 && tr[stk[k-1]].pri > tr[i].pri) k--;
//        if(k != 0)
//        {
//            tr[i].fat = stk[k-1];
//            tr[stk[k-1]].son[1] = i;
//        }
//        if(k != top)
//        {
//            tr[stk[k]].fat = i;
//            tr[i].son[0] = stk[k];
//        }
//        stk[k++] = i;
//        top = k;
//    }
//    return stk[0];
//}
//另外一种O(n)构建笛卡尔树的方式，特点是代码很短
int cartesian_build(int n)
{
    for(int i = 1; i <= n; i++)
    {
        int k = i - 1;
        while(tr[k].pri > tr[i].pri) k = tr[k].fat;
        tr[i].son[0] = tr[k].son[1];
        tr[k].son[1] = i;
        tr[i].fat = k;
        tr[tr[i].son[0]].fat = i;//很多人没加这句，父节点关系就会乱掉，但到目前为止交到OJ上不会发生错误，因为此时这个点已不在最右链上，不会用到其父节点了
    }
    return tr[0].son[1];
}
int dfs(int x)
{
    if(! x) return 0;
    int sz = dfs(tr[x].son[0]);
    sz += dfs(tr[x].son[1]);
    ans = max(ans, (ll)(sz + 1) * tr[x].pri);
    return sz + 1;
}
int main()
{
    int n, a;
    while(scanf("%d", &n), n)
    {
        tr[0].init(0, 0, 0);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a);
            tr[i].init(i, a, 0);
        }
        root = cartesian_build(n);
        ans = 0;
        dfs(root);
        printf("%lld\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88