OpenJudge Cartesian Tree

【代码】
 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int maxn = 50005;
 8 //Tkey为输入主键与辅键的结构体
 9 //key表示主键，aux表示辅键，index表示是输入的第几个结点
10 struct Tkey {
11     int key, aux, index;
12 } keys[maxn];
13 //Tnode是BST结点的结构体，key表示主键，aux表示辅键
14 //father表示父结点的编号，leftChild和rightChild表示左右儿子结点
15 struct Tnode {
16     int key, aux, father, leftChild, rightChild;
17 } node[maxn];
18 int n;
19 
20 //排序的比较函数
21 bool cmp(const Tkey &a, const Tkey &b) {
22     return a.key < b.key;
23 }
24 
25 int main() {
26     //读入数据
27     int i;
28     scanf("%d", &n);
29     for (i = 1; i <= n; ++i) {
30         scanf("%d%d", &keys[i].key, &keys[i].aux);
31         keys[i].index = i;
32     }
33 
34     //按key对结点排序
35     sort(keys + 1, keys + n + 1, cmp);
36 
37     //按key从小到大将结点插入BST
38     //father表示当前插入结点的父节点，leftChild表示当前插入结点的左儿子节点
39     //rightMost表示每次插入前BST最右的结点
40     int p, father, leftChild, rightMost = 0;
41     for (i = 1; i <= n; ++i) {
42         //寻找插入结点的父亲与左儿子
43         leftChild = 0; father = rightMost;
44         while (father != 0 && node[father].aux > keys[i].aux) {
45             leftChild = father;
46             father = node[father].father;
47         }
48         //将结点插入BST
49         p = keys[i].index;
50         node[p].key = keys[i].key;
51         node[p].aux = keys[i].aux;
52         node[p].father = father;
53         node[p].leftChild = leftChild;
54         node[p].rightChild = 0;
55         if (father != 0)
56             node[father].rightChild = p;
57         if (leftChild != 0)
58             node[leftChild].father = p;
59         rightMost = keys[i].index;
60     }
61 
62     //输出答案
63     printf("YES
");
64     for (i = 1; i <= n; ++i)
65         printf("%d %d %d
", node[i].father, node[i].leftChild, node[i].rightChild);
66     return 0;
67 }