SGU155(笛卡尔树的构造)
题目：http://acm.sgu.ru/problem.php?contest=0&problem=155
题意：给出每个点的两个值key和fix，且所有的key值和fix值都是不相同的，要求构造出笛卡尔树。输入每个点的两个权
值，输出笛卡尔树每个结点（按照输入的顺序编号）的父亲结点和两个儿子的编号。
分析：首先，笛卡尔树对于key来说是二叉搜索树，对于fix来说是最小堆，所以跟Treap一样。笛卡尔树在LCA和RMQ问题中有
着重要的应用。这题首先记录下每个结点的ID，然后以key为关键字排序。排完了之后就会有线性的构造笛卡尔树的算法了。
这里的笛卡尔树一定是存在的，所以先输出YES。
构造笛卡尔树的过程：
使用数据结构栈，栈中保存的始终是右链，即根结点、根结点的右儿子、根结点的右儿子的右儿子……组成的链，并且栈中从
栈顶到栈底key依次减小。
如果按照从后到前的顺序判断一个元素是否大于a[i]，则每次插入的时间复杂度为O(k+1)，k为本次插入中移除的右链元素个
数。因为每个元素最多进出右链各一次，所以整个过程的时间复杂度为O(n)。
#include <iostream>#include <string.h>#include <algorithm>#include <stdio.h>using namespace std;const int N=1000005;const int INF=~0U>>1;struct node{ int id; //id记录节点的编号，从1开始 int key,fix; //二元组 int pre,l,r; //分别表示当前节点的父亲，左儿子和右儿子 void clear() { pre=l=r=0; } bool operator < (node t) const { return key<t.key; }};node T[N];int stack[N],p[N],top;void Init(int n){ for(int i=1; i<=n; i++) T[i].pre=T[i].l=T[i].r=0; T[0].fix=-INF;}int Build(int n){ top=0; stack[++top]=1; for(int i=2; i<=n; i++) { while(top>=0&&T[i].fix<T[stack[top]].fix) --top; if(top) { T[i].pre=stack[top]; T[i].l=T[stack[top]].r; T[T[stack[top]].r].pre=i; T[stack[top]].r=i; stack[++top]=i; } else { T[stack[1]].pre=i; T[i].l=stack[1]; stack[++top]=i; } } return stack[1];}int main(){ int n; scanf("%d",&n); Init(n); for(int i=1; i<=n; i++) { scanf("%d%d",&T[i].key,&T[i].fix); T[i].id=i; } sort(T+1,T+n+1); int root=Build(n); for(int i=1; i<=n; i++) p[T[i].id]=i; puts("YES"); for(int i=1; i<=n; i++) printf("%d %d %d\n",T[T[p[i]].pre].id,T[T[p[i]].l].id,T[T[p[i]].r].id); return 0;}