[HNOI2004]宠物收养所

题目思路：splay，主要用到找某个数(不一定在树中)的前驱，后继，和插入，删除。

#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;

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;

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("%dn",ans);

}

}