笛卡尔树

一种二叉树,每个节点由 键值二元组 (k,w) 组成

---

性质

1. 数列中每个元素对应树中某个唯一节点,树节点也对应于数列中某个唯一元素

2. 中序遍历笛卡尔树得到原数列

   • 任意树节点的左子树中的节点对应的数组元素下标小于该节点对应数组元素下标
   • 同理, 右子树中的节点对应的数组元素下标大于该节点对应数组的元素下标

3. 由于具有堆的性质, 任意节点对应的数值 大于or小于 左or右子树内任意节点对应的数值

---

树的构造 流程图 OI_wiki

1. 将待插入元素按照键值排序, 因为键值逐渐变大,每次插入都是在树的右链上进行 (二叉搜索树的性质)

2. 根据堆的性质 找到此次插入元素 $i$ 在右链上的位置的父亲节点 Q,

   • 插入过程:

     1. 修改$i$的左节点 为 Q的右节点

     2. 修改 Q的右节点为 i

     3. 修改 $i$的父亲 以及 $i$左节点的父亲

---

HDU 1506

• 由于矩阵高度被最小矩形高度限制, 笛卡尔树构造按最小堆来
• 子树下标是一段连续区间

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;

struct node {
    int index,val,par,ch[2];
    node() {}
    node(int a,int b,int c):index(a),val(b),par(c) {
        ch[0] = ch[1] = 0;
    }
    bool operator< (node &temp) { return this->index<temp.index; }
} tree[maxn];

int root,top;
ll ans;

int build(int n) {
    for (int i=1; i<=n; ++i) {
        int k = i-1;
        // 在右链上根据值 找到 属于自己的位置
        while (tree[k].val > tree[i].val) k = tree[k].par;
        // 修改右链上的节点
        tree[i].ch[0] = tree[k].ch[1];
        tree[k].ch[1] = i;
        // 记录父亲节点
        tree[i].par = k;
        int i_right = tree[i].ch[0];
        tree[i_right].par = i;
    }
    // 返回0节点右儿子的编号,也就是真正的根节点
    return tree[0].ch[1];
}

int dfs(int x) {
    if (!x) return 0;
    int left  = tree[x].ch[0];
    int right = tree[x].ch[1];
    int size = dfs(left);
    size += dfs(right);
    // size+1 +1加上自己
    ans = max(ans,(size+1) * (ll)tree[x].val);
    return size+1;
}

int main() {
    int n,hi;
    while (cin >> n && n) {
        // 虚点,开始建树
        tree[0] = node(0,0,0);
        for (int i=1; i<=n; ++i) {
            cin >> hi;
            tree[i] = node(i,hi,0);
        }
        root = build(n);
        ans = 0;
        // 枚举树上的点
        dfs(root);
        cout << ans << endl;
    }
    return 0;
}