poj2828 伸展树模拟

用伸展树模拟插队比线段树快乐3倍。。

但是pojT了。别的oj可以过，直接贴代码.

每次更新时，找到第pos个人，splay到根，然后作为新root的左子树即可

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define maxn 200005

using namespace std;

int pre[maxn],ch[maxn][],num[maxn],key[maxn],size[maxn],tot,root;

void init(){

    tot=root=;

    pre[root]=ch[root][]=ch[root][]=num[root]=key[root]=size[root]=;

}

void newnode(int &r,int fa,int k,int val){

    r=++tot;

    ch[r][]=ch[r][]=;

    num[r]=val;

    key[r]=k;

    pre[r]=fa;

    size[root]=;

}

void pushup(int r){

    size[r]=size[ch[r][]]+size[ch[r][]]+;

}

void rotate(int x,int kind){

    int fa=pre[x];

    ch[fa][!kind]=ch[x][kind];

    pre[ch[x][kind]]=fa;

    if(pre[fa])

        ch[pre[fa]][ch[pre[fa]][]==fa]=x;

    pre[x]=pre[fa];

    pre[fa]=x;

    ch[x][kind]=fa;

    pushup(x);pushup(fa);

}

void splay(int r,int goal){

    while(pre[r]!=goal){

        if(pre[pre[r]]==goal) rotate(r,ch[pre[r]][]==r);

        else {

            int fa=pre[r];

            int kind=ch[pre[fa]][]==fa;//????????

            if(ch[fa][kind]==r){

                rotate(r,!kind);

                rotate(r,kind);

            }

            else {

                rotate(fa,kind);

                rotate(r,kind);

            }

        }

    }

    if(goal==) root=r;

    pushup(r);pushup(root);

}

void Treavel(int x)

{

    if(x)

    {

        Treavel(ch[x][]);

        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d \n",x,ch[x][],ch[x][],pre[x],size[x],key[x]);

        Treavel(ch[x][]);

    }

}

void debug()

{

    printf("root:%d\n",root);

    Treavel(root);

}

void Treval(int r){

    if(r){

        if(ch[r][]) Treval(ch[r][]);

        printf("%d ",num[r]);

        if(ch[r][]) Treval(ch[r][]);

    }

}

void getth(int pos){

    int r=root;

    while(size[ch[r][]]+!=pos){

        if(size[ch[r][]]+<pos)

            pos-=size[ch[r][]]+,r=ch[r][];

        else r=ch[r][];

    }

    splay(r,);

}

void insert(int pos,int val){//??

    if(root==) {

        newnode(root,,pos,val);

        return;

    }

    else if(pos==){

        int r=root;

        while(ch[r][])

            r=ch[r][];

        newnode(ch[r][],r,pos,val);

        splay(ch[r][],);

        return;

    }

    else {

        getth(pos);

        int oldroot=root;

        newnode(root,,pos,val);

        ch[root][]=ch[oldroot][];

        pre[ch[root][]]=root;

        ch[oldroot][]=;

        pushup(oldroot);

        ch[root][]=oldroot;

        pre[oldroot]=root;

        pushup(root);

    }

}

int main(){

    int n,pos,num;

    while(scanf("%d",&n)==){

        init();

        for(int i=;i<=n;i++){

            scanf("%d%d",&pos,&num);

            insert(pos,num);

            debug();

        }

        Treval(root);

        puts("");

    }

    return ;

}