[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.zzzyk.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);
&nbs
补充：软件开发 , C++ ,
