HNOI2002 營業額統計

題目思路：splay,用到了查找樹內某結點的前驅，後繼和插入操作。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define Max 40000 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
int p[Max],ch[Max][2],val[Max],root,top1; 
inline void newnode(int &x,int fa,int data) 
{ 
    x=++top1; 
    p[x]=fa,val[x]=data; 
    ch[x][0]=ch[x][1]=0; 
} 
inline void rot(int x,int f) 
{ 
    int y=p[x]; 
    ch[y][!f]=ch[x][f]; 
    p[ch[x][f]]=y; 
    if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x; 
    p[x]=p[y]; 
    ch[x][f]=y; 
    p[y]=x; 
} 
inline void splay(int x,int goal) 
{ 
    while(p[x]!=goal) 
    { 
        if(p[p[x]]==goal) 
            rot(x,ch[p[x]][0]==x); 
        else 
        { 
            int y=p[x]; 
            int f=(ch[p[y]][0]==y); 
            if(ch[y][f]==x) 
            { 
                rot(x,!f),rot(x,f); 
            } 
            else 
            { 
                rot(y,f),rot(x,f); 
            } 
        } 
    } 
    if(goal==0) root=x; 
} 
inline int pre(int x) 
{ 
    int tmp=ch[x][0]; 
    if(tmp==0) 
    return inf;   www.2cto.com
    while(ch[tmp][1]) 
    { 
        tmp=ch[tmp][1]; 
    } 
    return val[x]-val[tmp]; 
} 
inline int suc(int x) 
{ 
    int tmp=ch[x][1]; 
    if(tmp==0) 
        return inf; 
    while(ch[tmp][0]) 
        tmp=ch[tmp][0]; 
    return val[tmp]-val[x]; 
} 
inline int ins(int data) 
{ 
    int x=root; 
    while(ch[x][val[x]<data]) 
    { 
        if(val[x]==data) 
        { 
            splay(x,0); 
            return 0; 
        } 
        x=ch[x][val[x]<data]; 
    } 
    newnode(ch[x][val[x]<data],x,data); 
    splay(ch[x][val[x]<data],0); 
    return 1; 
} 
int main() 
{ 
    int n,a,b,ans,i,tmp; 
    while(scanf("%d",&n)!=EOF) 
    { 
        ans=0; 
        top1=0; 
        for(i=1;i<=n;i++) 
        { 
            if(scanf("%d",&tmp)==EOF) 
            tmp=0; 
            if(i==1) 
            { 
                newnode(root,0,tmp); 
                ans+=tmp;continue; 
            } 
            if(ins(tmp)==0)continue; 
            a=pre(root); 
            b=suc(root); 
            if(a<b) 
                ans+=a; 
            else 
                ans+=b; 
        } 
        printf("%d\n",ans); 
    } 
}