二叉堆，算法是固定的。地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=2201

#include <stdio.h>

typedef struct
{
    int k;
    int a;
    int left;
    int right;
    int parent;
}node;
node tree[50005];

int num[50005];

int judge(int a, int b)
{
    
    int ans;
    if(tree[num[a]].k>tree[num[b]].k)
    {
        ans = 1;
    }
    else if(tree[num[a]].k<tree[num[b]].k)
    {
        ans = -1;
    }
    else 
    {
        ans = 0;
    }
    return ans;
}

void swap(int a, int b)
{
    
    int t;
    
    t = num[a];
    num[a] = num[b];
    num[b] = t;
}

int partion(int low, int high, int p)
{
    
    while(low<=high)
    {
        if(low<p)
        {
            if(judge(low, p)>0)
            {
                swap(low, p);
                p = low;
            }
            low ++;
        }
        else
        {
            if(high>p)
            {
                if(judge(high, p)<0)
                {
                    swap(high, p);
                    p = high;
                }
            }
            high --;
        }
    }
    return p;
}

void qsort(int left, int right)
{
    int middle;
    if(left<right)
    {
        middle = (left+right) / 2;
        middle = partion(left, right, middle);
        qsort(left, middle-1);
        qsort(middle+1, right);
    }
}

void creat_tree(int n)
{

    int i;
    int p;
    int temp;
    
    qsort(0, n-1);
    tree[num[0]].left = tree[num[0]].parent = tree[num[0]].right = -1;
    for (i=1; i<n; i++)
    {
        p = num[i-1];
        while (tree[p].a>=tree[num[i]].a && tree[p].parent!=-1)
        {
            p = tree[p].parent;
        }

        if (tree[p].parent==-1 && tree[p].a>=tree[num[i]].a)
        {
            tree[num[i]].left = p;
            tree[num[i]].right = -1;
            tree[num[i]].parent = -1;
            tree[p].parent = num[i];
        }
        else
        {
            temp = tree[p].right;
            tree[p].right = num[i];
            tree[num[i]].left = temp;
            tree[num[i]].right = -1;
            tree[num[i]].parent = p;
            tree[temp].parent = num[i];
        }
    }
}

int main()
{

    int n;
    int i;
    while (scanf("%d", &n) != EOF)
    {
        for (i=0; i<n; i++)
        {
            scanf("%d%d", &tree[i].k, &tree[i].a);
            num[i] = i;
        }
        creat_tree(n);
        printf("YES\n");
        for (i=0; i<n; i++)
        {
            printf("%d %d %d\n", tree[i].parent+1, tree[i].left+1, tree[i].right+1);
        }
    }
    return 0;
}