笛卡尔树

<div class="O"> <div> 【问题描述】 </div> <div> &nbsp; &nbsp; &nbsp; 笛卡尔树(Cartesian Tree)是一种特殊的二叉搜索树。让我们复习一下：二叉搜索树是一颗有根二叉树，并且对于每个结点x都满足：它左子树中的任何结点的权值都小于x的权值，它右子树中任何结点的权值都大于x的权值。让我们形式化定义：假设x的左子树为L(x)，x的右子树为R(x)，x的权值为k(x)。则一颗满足如下条件的二叉树称为二叉搜索树： </div> <div> &nbsp; &nbsp; &nbsp;如果点y在L(x)中，则k(y)&lt;k(x)；如果点z在R(x)中，则k(z)&gt;k(x)。 </div> <div> &nbsp; &nbsp; &nbsp;一颗二叉搜索树称为笛卡尔树，当且仅当我们给每个点都附加一个权值a(x)，且每个点的a权值都严格小于它左右子树中的点的a权值。也就是说：如果点y是x的父亲，则a(y)&lt;a(x)。 </div> <div> &nbsp; &nbsp; &nbsp;因此，一颗笛卡尔树就是一颗二叉树，对于每个结点有两个权值(k,a)，且满足上面三条性质。 </div> <div> &nbsp; &nbsp; &nbsp;给定一个点，请你构造出一颗笛卡尔树。 </div> <div> </div> </div>

<div class="O"> <div> 第一行是一个整数n(1=&lt;n&lt;=50000)，表示给定结点的个数。 </div> <div> 接下来n行，每行两个整数k(i)，a(i)，表示点i的两个权值。题目保证同类权值不出现重复，也就是说对于任意i&lt;&gt;j，一定有k(i)&lt;&gt;k(j)，且a(i)&lt;&gt;a(j)。权值都是不超过50000的正整数。 </div> </div>

<div class="O"> <div> 第一行输出解的情况。如果可以构造出一颗笛卡尔树，输出"yes"，否则输出"no"。 </div> <div> 如果可以构造，那么接下来输出n行，每行3个整数，分别表示第i个结点的父亲、左儿子、右儿子的编号。顶点编号都是从1到n的，0表示空。顶点的输出顺序与输入顺序一致。 </div> </div>