splay tree-hnoi2002 营业额统计

多组数据，读到EOF的时候X=0//贼坑
n个点，每插入一个点找到之前插入的点之中和它相差最小的点，ans+=两者之差。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
const int oo=100000010;
int root,top,ans;
struct node{
    int l,r,f,w;
}tree[100010];
void New(int x,int father){
    tree[++top].w=x;
    tree[top].f=father;
    return;
}
int min(int  x,int y){
    if(x>y)return y;
    else return x;
}
void zig(int d){
    int fa=tree[d].f;
    int prefa=tree[fa].f;
    if(tree[prefa].l==fa)
        tree[prefa].l=d;
    else
        tree[prefa].r=d;
    tree[fa].f=d;
    tree[fa].l=tree[d].r;
    tree[d].f=prefa;
    if(tree[d].r)
        tree[tree[d].r].f=fa;
    tree[d].r=fa;
    return;
}
void zag(int d){
    int fa=tree[d].f;
    int prefa=tree[fa].f;
    if(tree[prefa].l==fa)
        tree[prefa].l=d;
    else
        tree[prefa].r=d;
    tree[fa].f=d;
    tree[fa].r=tree[d].l;
    tree[d].f=prefa;
    if(tree[d].l)
        tree[tree[d].l].f=fa;
    tree[d].l=fa;
    return;
}
void splay(int x){
    int d=root;
    while(1){
        if(x<tree[d].w){
            if(!tree[d].l)
                break;
            d=tree[d].l;
        }
        else {
            if(!tree[d].r)
                break;
            d=tree[d].r;
        }
    }

    New(x,d);
    if(x<tree[d].w)
        tree[d].l=top;
    else tree[d].r=top;

    while(tree[top].f){
        if(tree[top].f==root){
            if(tree[root].l==top)
                zig(top);
            else
                zag(top);
            break;
        }
        else {
            int fa=tree[top].f;
            int prefa=tree[fa].f;
            if(tree[fa].l==top){
                if(tree[prefa].l==fa)
                    zig(fa);
                zig(top);
            }
            else if(tree[fa].r==top){
                if(tree[prefa].r==fa)
                    zag(fa);
                zag(top);
            }
        }
    }
    root=top;
    return;
}
int find(int x){
    int d=root;
    while(1){
        if(x==tree[d].w)
            return 0;
        if(x<tree[d].w){
            if(!tree[d].l)
                return 1;
            d=tree[d].l;
        }
        else {
            if(!tree[d].r)
                return 1;
            d=tree[d].r;
        }
    }
    return 1;
}
int z(){
    int d=tree[root].l;
    if(!d)return oo;
    while(tree[d].r)
        d=tree[d].r;
    return tree[d].w;
}
int y(){
    int d=tree[root].r;
    if(!d)return oo;
    while(tree[d].l)
        d=tree[d].l;
    return tree[d].w;
}
void clear(int n){
    for(int i=0;i<=n;i++){
        tree[i].w=0;
        tree[i].f=0;
        tree[i].l=0;
        tree[i].r=0;
    }
}
int main(){
    int i,x,n;
    while(~scanf("%d",&n)){
        root=ans=top=0;
        for(i=1;i<=n;i++){
            if(scanf("%d",&x)==EOF)x=0;

            if(i==1){
                ans+=x;
                New(x,0);
                tree[0].l=1;
                root=top;
                continue;
            }
            if(!find(x))
                continue;

            splay(x);
            int x1=abs(x-z());
            int x2=abs(x-y());
            ans+=min(x1,x2);
        }
        printf("%d\n",ans);
        clear(n);
    }
    return 0;
}

In put
6
5
1
2
5
4
6
Out put
12