http://www.hhanger.com/?p=134

http://www.coderplusplus.com/?p=393

POJ 2201

const int N = 50010;int stack[N];int pre[N], lson[N], rson[N];struct node {    int key;    int val;    int id;} st[N];bool operator < (const node& a, const node& b) {    return a.key < b.key;}void init(int n) {    memset(stack, -1, sizeof(stack));    memset(pre, 0, sizeof(pre));    for(int i = 0; i <= n; ++i) {        lson[i] = rson[i] = 0;    }}void build_cartesian_tree(int n) {    int i, k, top = -1;    for(i = 0; i < n; ++i) {        k = top;        while(k >= 0 && st[stack[k] + 1].val > st[i + 1].val)   --k;        if(k != -1) {            pre[st[i + 1].id] = st[stack[k] + 1].id;            rson[st[stack[k] + 1].id] = st[i + 1].id;        }        if(k < top) {            pre[st[stack[k + 1] + 1].id] = st[i + 1].id;            lson[st[i + 1].id] = st[stack[k + 1] + 1].id;        }        stack[++k] = i;        top = k;    }    pre[st[stack[0] + 1].id] = 0;}int main() {    //freopen("data.in", "r", stdin);    int n, i;    while(~scanf("%d", &n)) {        init(n);        for(i = 1; i <= n; ++i) {            scanf("%d%d", &st[i].key, &st[i].val);            st[i].id = i;        }        sort(st + 1, st + n + 1);        build_cartesian_tree(n);        puts("YES");        for(i = 1; i <= n; ++i) {            printf("%d %d %d\n", pre[i], lson[i], rson[i]);        }    }    return 0;}