笛卡尔树 Cartesian tree

给个板子题

笛卡尔树是这样的一种数据结构：对于 \(n\) 个二元组 \((key, value)\) 形成的笛卡尔树，满足如下性质

其 \(key\) 值满足二叉搜索树性质 (中序排列单调递增)，\(value\) 值满足堆性质

给出若干个 \((key, value)\) 二元组，采取以下方式构建一颗笛卡尔树 (以大根堆笛卡尔树为例)

将二元组按照 \(key\) 值排序，并逐个添加进笛卡尔树中，且添加的位置一定是某个 最右结点 (即从根往右第一个没有右儿子的结点)，这是为了满足二叉搜索树的性质

若当前待添加结点 \(value\) 大于根的 \(value\) ，则将其设为根，并将原来的根作为其左儿子
否则，从根往 右 走，直到找到某个结点 \(w\) 的 \(value\) 小于待添加结点，则将待添加结点取代 \(w\) 的位置并将 \(w\) 作为该节点的左儿子
若找不到 \(value\) 比待添加结点小的结点，则将其作为最右结点的右儿子接入

在实际代码编写中，第二种情况与第三种情况可以合并

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

const int MAX_N = 51000;

string lab[MAX_N];

int son[MAX_N][2], pri[MAX_N];

int root;

struct Node {

    string l; int p;

    Node(){}

    Node(string _l, int _p) : l(_l), p(_p) {}

    bool operator < (const Node& c) const { return l < c.l; }

} a[MAX_N];

inline int toInt(string s) {

    int res = 0;

    for (int i = 0; i < s.size(); ++i) {

        res *= 10;

        res += (s[i] - '0');

    }

    return res;

}

void dfs(int p) {

    cout << '(';

    if (son[p][0])

        dfs(son[p][0]);

    cout << lab[p] << '/' << pri[p];

    if (son[p][1])

        dfs(son[p][1]);

    cout << ')';

}

int main() {

    int n;

    while (cin >> n) {

        if (n == 0) break;

        for (int i = 1; i <= n; ++i)

            son[i][0] = son[i][1] = 0;

        root = 0;

        for (int i = 1; i <= n; ++i) {

            string node;

            cin >> node;

            int pos = node.find('/');

            a[i] = Node(node.substr(0, pos), toInt(node.substr(pos + 1)));

        }

        sort(a + 1, a + n + 1);

        for (int cur = 1; cur <= n; ++cur) {

            lab[cur] = a[cur].l;

            pri[cur] = a[cur].p;

            if (!root || pri[cur] >= pri[root]) {

                son[cur][0] = root;

                root = cur;

            } else {

                int p = root;

                while (son[p][1] && pri[son[p][1]] > pri[cur])  p = son[p][1];

                son[cur][0] = son[p][1];

                son[p][1] = cur;

            }

        }

        dfs(root);

        cout << endl;

    }

    return 0;

}

笛卡尔树 Cartesian tree的相关教程结束。