例①、POJ 2201：
题目：
笛卡尔树：笛卡尔树中的每个节点有两个数据域key，val，对于数据域key，满足二叉搜索树性质，对于数据域val，满足最小堆性质。给出N个节点，1<=N<=50000，每个节点由一对key，val构成，判断能否根据这些节点构建一颗笛卡尔树，如果可以构建则输出构造出的笛卡尔树，否则输出“NO”。

解题思路：首先，根据N个节点，肯定可以构造出一颗笛卡尔树。

//本来是按照val排序，然后建立搜索二叉树，T了
//学了笛卡尔之后才知道，它是按照key排序，然后O（n）建树
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=50100;
const int inf=0x3f3f3f3f;
struct node
{
    int l,r,fa;
    int val,key;
    int id;
    bool operator <(const node &b) const
    {
        return key<b.key;
    }
}t[maxn];
int l[maxn],r[maxn],fa[maxn];
void init(void)
{
    t[0].l=t[0].r=0;
    t[0].val=-inf;
    t[0].fa=0;
    t[0].id=0;
}

void _insert(int x)
{
    int now=x-1;
    while(t[now].val>t[x].val) now=t[now].fa;
    t[x].l=t[now].r;
    t[t[now].r].fa=x;

    t[x].fa=now;
    t[now].r=x;
}

void dfs(int x)
{
    if(!x) return ;
    l[t[x].id]=t[t[x].l].id;
    r[t[x].id]=t[t[x].r].id;
    fa[t[x].id]=t[t[x].fa].id;
    dfs(t[x].l);
    dfs(t[x].r);
}

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        init();
        for(int i=1;i<=n;i++)
            scanf("%d%d",&t[i].key,&t[i].val),t[i].id=i;
        sort(t+1,t+n+1);
        for(int i=1;i<=n;i++)
            _insert(i);
        printf("YES\n");
        dfs(t[0].r);
        for(int i=1;i<=n;i++)
            printf("%d %d %d\n",fa[i],l[i],r[i]);

    }
    return 0;
}

例②、P5854 【模板】笛卡尔树
题目描述
给定一个 1∼n 的排列 p，构建其笛卡尔树。

即构建一棵二叉树，满足：

每个节点的编号满足二叉搜索树的性质。
节点 i 的权值为 pi ，每个节点的权值满足小根堆的性质。

输入格式
第一行一个整数 n。

第二行一个排列 p1…n 。

输出格式
设 li,ri 分别表示节点 i 的左右儿子的编号（若不存在则为 0）。

一行两个整数，分别表示 xor_sum of i * (li+1) , xor_sum of i * (ri+1)

输入输出样例
输入 #1 复制
5
4 1 3 2 5
输出 #1 复制
19 21

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;

char buffer[100001],*S,*T;
inline char Get_Char()
{
    if (S==T)
    {
        T=(S=buffer)+fread(buffer,1,100001,stdin);
        if (S==T) return EOF;
    }
    return *S++;
}
inline int read()
{
    char c;int re=0;
    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
    while(c>='0'&&c<='9') re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    return re;
}


const int maxn=10000100;
const int inf=0x3f3f3f3f;
struct node
{
    int l,r,fa;
    int val;
}t[maxn];
void init(void)
{
    t[0].l=t[0].r=0;
    t[0].val=-inf;
    t[0].fa=0;
}

void _insert(int x)
{
    int now=x-1;
    while(t[now].val>t[x].val) now=t[now].fa;
    t[x].l=t[now].r;
    t[t[now].r].fa=x;

    t[x].fa=now;
    t[now].r=x;
}


int main(void)
{
    int n;
    init();
    n=read();
    for(int i=1;i<=n;i++)
        t[i].val=read(),_insert(i);
    ll ansl=0,ansr=0;
    for(ll i=1;i<=n;i++)
        ansl^=i*(t[i].l+1),ansr^=i*(t[i].r+1);
    printf("%lld %lld\n",ansl,ansr);

    return 0;
}