题目：笛卡尔树：笛卡尔树中的每个节点有两个数据域k，a，对于数据域k，满足二叉搜索树性质，对于数据域a，满足最小堆性质。给出N个节点，1<=N<=50000，每个节点由一对k，a构成，判断能否根据这些节点构建一颗笛卡尔树，如果可以构建则输出构造出的笛卡尔树，否则输出“NO”。
解题思路：首先，根据N个节点，肯定可以构造出一颗笛卡尔树。
参考博客：https://www.cnblogs.com/pushing-my-way/archive/2012/08/24/2653709.html
https://blog.csdn.net/lijiecsu/article/details/7490666
https://blog.csdn.net/faithdmc/article/details/37604441
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
struct S{
int id,key,val,parent,l,r;
}node[50005];
bool cmp(struct S a,struct S b)
{
return a.key<b.key;
}
int stk[50005],top,p[50005],l[50005],r[50005];
void build(int n)//因为已经按key值升序排序了，所以后面加入的节点要么成为某个节点的右儿子，要么让根节点成为自己的左儿子
{
int i;
top=0;
stk[top]=1;
for(i=2;i<=n;i++)
{
while(top>=0 && node[stk[top]].val>node[i].val) top--;
if(top>-1)//如果找到一个不大于自己的节点，就成为该节点的右儿子，还要注意让该节点原来的右儿子变成自己的左儿子(key比其大并且小于其val)
{
node[i].parent=stk[top];
node[node[stk[top]].r].parent=i;
node[i].l=node[stk[top]].r;
node[stk[top]].r=i;
}
else//如果没找到不大于自己的节点，就变成新的根
{
node[stk[0]].parent=i;
node[i].l=stk[0];
}
stk[++top]=i;
}
}
int main()
{
int n,i;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
{
scanf("%d%d",&node[i].key,&node[i].val);
node[i].id=i;
node[i].parent=node[i].l=node[i].r=0;//初始化
}
sort(node+1,node+n+1,cmp);
build(n);
for(i=1;i<=n;i++)
{
p[node[i].id]=node[node[i].parent].id;
l[node[i].id]=node[node[i].l].id;
r[node[i].id]=node[node[i].r].id;
}
printf("YES\n");
for(i=1;i<=n;i++) printf("%d %d %d\n",p[i],l[i],r[i]);
}
return 0;
}
