构建

例题，POJ - 2201 Cartesian Tree

// 关键点
// int id[N], key[N], value[N];
// int ch[N][2], parent[N], stk[N];
// int tt;
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int id[N], key[N], value[N];
int ch[N][2], parent[N], stk[N];
int tt;
int n;
bool cmp(int i, int j){
    return key[i] < key[j];
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> key[i] >> value[i];
        id[i] = i;
    }
    sort(id + 1, id + 1 + n, cmp);
    for (int s = 1; s <= n; s++){
        int i = id[s];
        int j, p = 0;  // p表示刚刚退出栈的, 题意无儿子用0代替
        while (tt > 0 && value[stk[tt]] > value[i]){
            j = stk[tt--];      // 刚刚退出栈的是谁
            ch[j][1] = p;       // 刚刚退栈的右儿子赋值成上一个退掉的p
            parent[p] = j;      // 上一个退栈的父亲是j
            p = j;              // p更新，进行下一轮
        }
        ch[i][0] = p;   // 左儿子等于上一个退栈的p
        parent[p] = i;
        stk[++tt] = i;  // i加入栈里
    }
    // 最后清空一下栈的里东西
    int j, p = 0;
    while (tt > 0){
        j = stk[tt--];
        ch[j][1] = p;
        parent[p] = j;
        p = j;
    }
    // 笛卡尔树的构造方式，决定了肯定有解
    cout << "YES" << '\n';
    for (int i = 1; i <= n; i++)
        cout << parent[i] << ' ' << ch[i][0] << ' ' << ch[i][1] << '\n';
    return 0;
}