[HNOI2004]宠物收养所

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

[cpp]
#include
#include
#include
#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 }
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] x=ch[x][val[x] }
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] x=ch[x][val[x] }
return tmp;
}
void ins(int a)
{
int x=root;
while(ch[x][val[x] newnode(ch[x][val[x] splay(ch[x][val[x] }
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);
}
}