单调栈构造笛卡尔树

其实这个是来自于ZOJ的一道ACM题目

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2452

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。

以第一关键字 main_key 排升序，O(n*log(n));
单调栈的应用，O(n)时间构造笛卡尔树;
构造的时候只需要维护父节点即可，在最后可以遍历一遍所有节点由父节点和子节点的main_key比较来确定是左子还是右子;

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define mpair make_pair
#define pii pair<int,int>
#define MM(a,b) memset(a,b,sizeof(a));
typedef long long lld;
typedef unsigned long long u64;
template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
#define maxn 50020

int n;
struct Node{
    int id,mkey,akey;
    void init(int i){
        id= i; scanf(“%d%d”, &mkey, &akey);
    }
    bool operator<(Node b)const{
        return mkey<b.mkey;
    }
} a[maxn];

int stack[maxn];
int fa[maxn], ch[maxn][2];
void Build_Cartesian_Tree(){
    int i,k,top= 0;
    stack[0]= 0; // As the father of root;
    for(i=1;i<=n;++i){
        k= top;
        while( k>0 && a[ stack[k] ].akey > a[i].akey )
            –k;
        if( top==k ){
            fa[i]= stack[k];
            stack[++k]= i;
        }
        else if( top>k ){
            fa[ stack[k+1] ]= i;
            fa[i]= stack[k];
            stack[++k]= i;
        }
        top= k;
    }

    for(i=1;i<=n;++i) ch[i][0]= ch[i][1]= 0;
    for(i=1;i<=n;++i){
        if( a[ fa[i] ].mkey > a[i].mkey ) ch[ fa[i] ][0]= i;
        else ch[ fa[i] ][1]= i;
    }
}

int f[maxn], c[maxn][2];
void output(){
    a[0].id= 0; ///
    for(int i=1;i<=n;++i){
        f[ a[i].id ]= a[ fa[i] ].id;
        c[ a[i].id ][0]= a[ ch[i][0] ].id;
        c[ a[i].id ][1]= a[ ch[i][1] ].id;
    }
    puts(“YES”);
    for(int i=1;i<=n;++i) printf(“%d %d %d\\n”, f[i], c[i][0], c[i][1] );
}

int main()
{
    while( scanf(“%d”, &n) != EOF ){
        for(int i=1;i<=n;++i)
            a[i].init( i );

        sort( a+1, a+1+n );
        Build_Cartesian_Tree();
        output();
    }
}