首页 > 代码库 > [poj2201]Cartesian Tree(笛卡尔树)

[poj2201]Cartesian Tree(笛卡尔树)

题目链接:http://poj.org/problem?id=2201

就是给你key和value,建出笛卡尔树。感觉笛卡尔树的建树过程真的优美,按key排序后,每次插入一个点,相当于从根一直向右走的路径上,找到value小于当前点value,并且value最大的点,插入即可,具体看代码吧。

区分笛卡尔式和treap:两者都有key和value,都既满足二叉搜索树的性质,也满足堆的性质,但treap是用value去维护树的平衡,而笛卡尔树的value是我们已知的(好像是吧)。

 

技术分享
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define per(i,x,y) for (int i=(x);i>=(y);i--)
const int N=50010;
struct node{int key,val,id;}a[N];
int n,s[N],l[N],r[N],fa[N];
int read() {int d=0,f=1; char c=getchar(); while (c<0||c>9) {if (c==-) f=-1; c=getchar();} while (c>=0&&c<=9) d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;}
bool cmp(node a,node b){return a.key<b.key;}
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++) fa[i]=l[i]=r[i]=0;
        for (int i=1;i<=n;i++) a[i].key=read(),a[i].val=read(),a[i].id=i;
        sort(a+1,a+1+n,cmp);
        int k,top=0;
        for (int i=1;i<=n;i++)
        {
            k=top;
            while (k>0&&a[i].val<a[s[k]].val) k--;
            if (k)
            {
                fa[a[i].id]=a[s[k]].id;
                r[a[s[k]].id]=a[i].id;
            }
            if (k<top)
            {
                fa[a[s[k+1]].id]=a[i].id;
                l[a[i].id]=a[s[k+1]].id;
            }
            s[++k]=i;
            top=k;
        }
        fa[a[s[1]].id]=0;
        puts("YES");
        for (int i=1;i<=n;i++) printf("%d %d %d\n",fa[i],l[i],r[i]);
    }
    return 0;
}
View Code

 

[poj2201]Cartesian Tree(笛卡尔树)