[HNOI2004]寵物收養所

題目思路：splay，主要用到找某個數(不一定在樹中)的前驅，後繼，和插入，刪除。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#define mod 1000000 
using namespace std; 
#define inf 0x3f3f3f3f 
#define Max 84000 
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],top1,ans,val[Max],root; 
int num[2]; 
void debug(); 
void newnode(int &x,int fa,int data) 
{ 
    x=++top1; 
    p[x]=fa; 
    val[x]=data; 
    ch[x][0]=ch[x][1]=0; 
} 
void init() 
{ 
    top1=0;ans=0; 
    newnode(root,0,-inf); 
    newnode(ch[root][1],root,inf); 
    num[0]=num[1]=0; 
} 
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; 
    if(p[x]==0) 
    root=x; 
} 
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) root=x; 
} 
int pre(int a) 
{ 
    int x=root; 
    int tmp; 
    while(x) 
    { 
        if(val[x]==a) 
            return x; 
        if(val[x]<a) tmp=x; 
        x=ch[x][val[x]<a]; 
    } 
    return tmp; 
} 
int suc(int a) 
{ 
 
    int x=root; 
    int tmp; 
    while(x) 
    { 
        if(val[x]==a) 
            return x; 
        if(val[x]>a) tmp=x;//為什麼不用加v[x]<v[tmp],因為當遇到一個大於a的數時會一直向左走直到遇到小於a的數，而從遇到大於a的數後，數值都會比那個數小，也就是說後面找到的數一定越來越小。所以不用加，加的情況是找不到後繼且原來建樹沒有加兩個極值點。 
        x=ch[x][val[x]<a]; 
    } 
    return tmp; 
} 
void ins(int a) 
{ 
    int x=root; 
    while(ch[x][val[x]<a]) x=ch[x][val[x]<a];//找到加點的位置，即前驅和後繼的這前。 
    newnode(ch[x][val[x]<a],x,a);//將結點插入 
    splay(ch[x][val[x]<a],0); 
} 
void del(int x) 
{ 
    splay(x,0); 
    int tmp=ch[root][1]; 
    while(ch[tmp][0]) tmp=ch[tmp][0];//找根結點的後繼 
    splay(tmp,root);//將後繼伸展到根下面，這時成為了根結點的右兒子。 
    ch[tmp][0]=ch[root][0];//將後繼作為根結點，根結點刪除 
    p[ch[root][0]]=tmp; 
    p[tmp]=0;     www.2cto.com
    root=tmp; 
} 
int main() 
{ 
    int n,ty,a; 
    while(scanf("%d",&n)!=EOF) 
    { 
        init(); 
        while(n--) 
        { 
            scanf("%d%d",&ty,&a); 
 
            if(num[!ty]) 
            { 
                int tmp1=pre(a),tmp2=suc(a); 
                if(a-val[tmp1]<=val[tmp2]-a) 
                { 
                    ans+=a-val[tmp1]; 
                    ans%=mod; 
                    del(tmp1); 
                    num[!ty]--; 
                } 
                else 
                { 
                    ans+=val[tmp2]-a; 
                    del(tmp2); 
                    ans%=mod; 
                    num[!ty]--; 
                } 
            } 
            else 
            { 
                num[ty]++; 
                ins(a); 
            } 
        } 
        printf("%d\n",ans); 
    } 
}