平衡二叉树的入门题,最近在研究splay,就做了下,感觉题目不错,就写了。
这题就是简单的元素插入删除操作,注意一下绝对值相同的时候取较小的即可,还有就是每次收养所里要么都是人,要么都是宠物。
这里用到一个type变量记录树种元素是人还是宠物,如果是-1表示空
这样每次取得一个数,如果和树种类型一致,就加入树种,否则就在树中寻找绝对值离它最近点一个即可。
代码写的比较长,有些是这道题不需要的函数,主要是为了封装,全部写了出来,可以当模板用。只是多元素的处理没有弄好,如果有重复元素,rank和selete函数以及结构体的封装就要换一下了。
我的代码:
y=x->fa;
y->son[1-w]=x->son[w];
if(x->son[w]!=null){
x->son[w]->fa=y;
}
x->fa=y->fa;
if(y->fa!=null){
if(y==y->fa->son[0]){
y->fa->son[0]=x;
}else{
y->fa->son[1]=x;
}
}
x->son[w]=y;
y->fa=x;
update(y);
update(x);
}
void splay(Node* x,Node* y){
while(x->fa!=y){
if(x->fa->fa==y){
if(x==x->fa->son[0]){
rotate(x,1);
}else{
rotate(x,0);
}
}else{
if(x->fa==x->fa->fa->son[0]){
if(x==x->fa->son[0]){
rotate(x->fa,1);
rotate(x,1);
}else{
rotate(x,0);
rotate(x,1);
}
}else{
if(x==x->fa->son[1]){
rotate(x->fa,0);
rotate(x,0);
}else{
rotate(x,1);
rotate(x,0);
}
}
}
}
if(y==null){
root=x;
}
}
void addNode(Node* x,Node* father,keyType val){
x->key=val;
x->fa=father;
x->son[0]=x->son[1]=null;
x->size=1;
}
void insert(keyType x){
Node *y, *z;
if(root==null){
y=New();
root=y;
addNode(y,null,x);
return;
}
y=root;
do{
y->size++;
if(x<y->key){
if(y->son[0]!=null){
y=y->son[0];
}else{
z=New();
addNode(z,y,x);
y->son[0]=z;
y=z;
break;
}
}else{
if(y->son[1]!=null){
y=y->son[1];
}else{
z=New();
addNode(z,y,x);
y->son[1]=z;
y=z;
break;
}
}
}while(true);
splay(y,null);
}
Node* find(keyType x){
Node* y;
y=root;
do{
if(y->key==x){
break;
}
if(x<y->key){
if(y->son[0]==null){
break;
}else{
y=y->son[0];
}
}else{
if(y->son[1]==null){
break;
}else{
y=y->son[1];
}
}
}while(true);
splay(y,null);
return y;
}
bool exist(keyType x){
Node* y;
y=root;
while(y!=null&&y->key!=x){
if(x<y->key){
y=y->son[0];
}else{
y=y->son[1];
}
}
if(y!=null)
splay(y,null);
return y!=null;
}
void init(){
nil.size=0;
null=&nil;
K=0;
top=0;
root=null;
}
void Delete(keyType x){
Node *y, *z;
y=find(x);
splay(y,null);
if(y->son[0]==null){
if(y->son[1]==null){
init();
}else{
root=y->son[1];
y->son[1]->fa=null;
}
}else{
z=y->son[0];
while(z->son[1]!=null)
z=z->son[1];
splay(z,y);
z->son[1]=y->son[1];
if(y->son[1]!=null){
y->son[1]->fa=z;
};
z->fa=null;
root=z;
update(z);
}
}
keyType selete(int x){
Node* y;
y=root;
while(1){
if(x<=y->son[0]->size){
y=y->son[0];
}else{
if(x==y->son[0]->size+1){
break;
}else{
x=x-y->son[0]->size-1;
y=y->son[1];
}
}
}
splay(y,null);
return y->key;
}
void deleteNums(keyType x){
Node* y;
if(root==null){
return;
}
y=find(x);
splay(y,null);
y->son[1]=null;
if(y->key>=x){
if(y->son[0]==null){
init();
}else{
root=y->son[0];
y->son[0]->fa=null;
}
}
}
int rank(keyType x){
Node* y;
if(root==null){
return 0;
}
y=find(x);
splay(y,null);
return y->son[0]->size+(int)(y->key<=x);
}
keyType maxSmall(keyType x){
Node* y;
if(root==null){
return -oo;
}
y=find(x);
splay(y,null);
if(y->key>x){
y=y->son[0];
if(y==null){
return -oo;
}
while(y->son[1]!=null){
y=y->son[1];
}
}
return y->key;
}
keyType minBig(keyType x){
Node* y;
if(root==null){
return oo;
}
y=find(x);
splay(y,null);
if(y->key<x){
y=y->son[1];
if(y==null){
return oo;
}
while(y->son[0]!=null){
y=y->son[0];
}
}
return y->key;
}
int cnt,ret;
void run(int x){
int t1,t2;
t1=minBig(x);
t2=maxSmall(x);
if(t1==oo){
ret=(ret+abs(x-t2))%mod;
Delete(t2);
cnt--;
}
else if(t2==-oo){
ret=(ret+abs(x-t1))%mod;
Delete(t1);
cnt--;
}
else if(abs(x-t1)<abs(x-t2)){
ret=(ret+abs(x-t1))%mod;
Delete(t1);
cnt--;
}
else if(abs(x-t1)==abs(x-t2)){
if(t1<t2){
ret=(ret+abs(x-t1))%mod;
Delete(t1);
cnt--;
}else{
ret=(ret+abs(x-t2))%mod;
Delete(t2);
cnt--;
}
}else{
ret=(ret+abs(x-t2))%mod;
Delete(t2);
cnt--;
}
}
int main(){
int n;
int x,op;
int type;
while(~scanf("%d",&n)){
init();
type=-1;
cnt=0;
ret=0;
for(int i=0;i<n;i++){
scanf("%d%d",&op,&x);
if(type==-1||type==op){
type=op;
insert(x);
cnt++;
}else{
run(x);
if(!cnt){
type=-1;
}
}
}
printf("%d/n",ret);
}
return 0;
}