给出节点两个关键值，按主关键值成BST，按副关键值成Heap——其实就是把节点排成Treap。只需要建立，不需要删除。
　　Submit 1: TLE on 15。修改一下结构吧。
　　Submit 2: TLE on 15。上述算法有可能退化到O(n^2)。
　　如果给出的节点按k值递增，那么构造Cartesian Tree有O(n)的算法（From 周源）：
　　首先可以认为在[1, 1]范围内建立一颗笛卡尔树是“平凡”的：不过是一个根节点而已。假设已经在[1, i-1]范围内建立了一个笛卡尔树，（i>1），那么我们试图得到[1, i]范围内的笛卡尔树。由于这颗树中有排序树的性质，所以可以沿着根节点不停的向右孩子走，直到无路可走，就把第i个节点挂在当且节点的右边：但是这样显然不一定会满足“二叉堆”的性质。如果第i个点的a值足够的大，那么二叉堆的性质并不会被破坏；但是如果小于其父亲的a值，在二叉堆的算法中，就需要一个shift(i)过程，但在这里会破坏排序树的美好性质。所以，我们就必须使用平衡排序二叉树算法中的左旋过程：Left-Rotate[father(i)]，对其进行一次左旋，就可以消除冲突。但是此时i点上升了一层，可能会和原来i的父亲的父亲产生冲突，那么继续进行左旋，直到没有冲突，就得到了新的笛卡尔树了。
　　乍一看这个算法，每个点可能最多会被左旋N次，最坏情况下的复杂度岂不是O(N^2)。但事实上，从“平摊”的角度分析，考察这颗动态树的最右边那条链，每个点最多会进入一次右链，也就最多会出一次。如果维护一个最右边的节点，那么插入一个节点的时间复杂度为O(1)，而某一个节点退出右链的时间复杂度显然是O(1)。所以整个算法的时间复杂度就是O(N)。
　　原题给出的数据是无序的，但可以用O(nlogn)的排序算法，将整体复杂度稳定在O(nlogn)。
　　Submit 3: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <cstdio>
#include <algorithm>
using namespace std;
 
struct node
{
    int id,k,a;
};
 
bool operator <(const node &a,const node &b)
{
    return a.k<b.k;
}
 
node tree[50001];
int p[50001],left[50001],right[50001],pos[50001];
 
void rotate(int i)
{
    while (p[i] && tree[i].a<tree[p[i]].a)
    {
        right[p[i]]=left[i];
        if (left[i]) p[left[i]]=p[i];
        left[i]=p[i];
        p[i]==left[p[p[i]]]?left[p[p[i]]]=i:right[p[p[i]]]=i;
        p[i]=p[p[i]];
        p[left[i]]=i;
    }
}
 
int main()
{
    right[0]=1;
    int n,rightmost(1);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        tree[i].id=i;
        scanf("%d%d",&tree[i].k,&tree[i].a);
    }
    sort(tree+1,tree+n+1);
    for (int i=1;i<=n;i++) pos[tree[i].id]=i;
    for (int i=2;i<=n;i++)
    {
        right[rightmost]=i; p[i]=rightmost; rightmost=i;
        rotate(i);
    }
    printf("YES\n");
    for (int i=1;i<=n;i++)
        printf("%d %d %d\n",tree[p[pos[i]]].id,tree[left[pos[i]]].id,tree[right[pos[i]]].id);
    return 0;
}