SGU155 笛卡尔树

题意：

给定N个二元组(Ki,Ai)

让你建立一棵笛卡尔树。

这个笛卡尔树实际上就是一个Treap.

k为二叉排序树的关键字，a为堆的关键字，堆是一个小根堆。

分析：

直接Treap会TLE,因为他给定了关键值，会退化成O(n^2)

然后我们可以根据Ki把结点从小到大排序，

然后每次都是最右边插入新的结点，

然后维护只需要左旋（他们叫右旋= =我觉得向左比较形象）

只有左旋的话我们可以注意到两个性质：

1、那么就是旋转以后，我这个结点不会增加新的儿子。

2、旋转以后，我必然是下一次插入的点的父结点。

别问我问什么。。。手画一下。。。证明这东西不是我这个级别做的事

然后我们可以注意到，从根开始连续向右到底这条路径可以看成一个栈！

每次左旋，就是一次出栈操作。

每次加结点，就是一次入栈操作。

于是，加结点和左旋操作数都<=n

所以，证明了这个算法的复杂度是：O(N)！

  

HINT

1A。

code：

#include #include #define N 60000
using namespace std;
struct re{int k,a,wz;}d[N];
struct trtype{int l,r,fa,zz;}tr[N];
int n,tot,mr,locate[N];

void left(int t){
    int p=tr[t].fa;
    tr[p].r=tr[t].l;
    tr[tr[t].l].fa=p;
    tr[t].l=p;
    tr[0].l=0; tr[0].r=0; tr[0].fa=0; tr[0].zz=0;
    if (tr[tr[p].fa].l==p) tr[tr[p].fa].l=t;
    if (tr[tr[p].fa].r==p) tr[tr[p].fa].r=t;
    tr[t].fa=tr[p].fa;
    tr[p].fa=t;
}   

void work(){
    tot=1; mr=1; tr[1].l=0; tr[1].r=0; tr[1].fa=0; tr[1].zz=1;
    for (int i=2;i<=n;i++){
        tot++;
        tr[tot].l=0; tr[tot].r=0; tr[tot].zz=i; tr[tot].fa=mr; tr[mr].r=tot;
        mr=tot;
        int now=tot;
        while (tr[now].fa!=0 && d[tr[tr[now].fa].zz].a>d[i].a)
          left(now);
    }   
}   

inline int wz(int x){
    return d[tr[x].zz].wz;
}   

void print(){
    printf("YESn");
    for (int i=1;i<=tot;i++) locate[d[tr[i].zz].wz]=i;
    for (int i=1;i<=n;i++){
        int t=locate[i];
        printf("%d %d %dn",wz(tr[t].fa),wz(tr[t].l),wz(tr[t].r));
    }   
}   

bool cmp(re x,re y){
    if (x.k    return false;
}   

int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&d[i].k,&d[i].a);
        d[i].wz=i;
    }
    sort(&d[1],&d[n+1],cmp);
    work();
    print();
    return 0;
}