学步园

平衡二叉树的入门题，最近在研究splay，就做了下，感觉题目不错，就写了。

这题就是简单的元素插入删除操作，注意一下绝对值相同的时候取较小的即可，还有就是每次收养所里要么都是人，要么都是宠物。

这里用到一个type变量记录树种元素是人还是宠物，如果是-1表示空

这样每次取得一个数，如果和树种类型一致，就加入树种，否则就在树中寻找绝对值离它最近点一个即可。

代码写的比较长，有些是这道题不需要的函数，主要是为了封装，全部写了出来，可以当模板用。只是多元素的处理没有弄好，如果有重复元素，rank和selete函数以及结构体的封装就要换一下了。

我的代码：

#include <cstdio><br /> #include <cstring><br /> #include <cstdlib><br /> #include <algorithm><br /> using namespace std;<br /> const int mod=1000000;<br /> const int MAX=150000;<br /> const int oo=0x3f3f3f3f;<br /> typedef int keyType;<br /> struct Node{<br /> keyType key;<br /> int size;<br /> Node* son[2];<br /> Node* fa;<br /> }node[MAX],nil,*null;<br /> Node* root;<br /> int st[MAX],top,K;<br /> Node* New(){<br /> if(top){<br /> return &node[st[--top]];<br /> }else{<br /> return &node[K++];<br /> }<br /> }<br /> void Delete(Node* ptr){<br /> st[top++]=ptr-node;<br /> }<br /> void update(Node* x){<br /> x->size=1;<br /> for(int i=0;i<2;i++){<br /> if(x->son[i]!=null){<br /> x->size+=x->son[i]->size;<br /> }<br /> }<br /> }<br /> void rotate(Node* x,const int& w){<br /> Node* y;</p> <p> y=x->fa;<br /> y->son[1-w]=x->son[w];<br /> if(x->son[w]!=null){<br /> x->son[w]->fa=y;<br /> }<br /> x->fa=y->fa;<br /> if(y->fa!=null){<br /> if(y==y->fa->son[0]){<br /> y->fa->son[0]=x;<br /> }else{<br /> y->fa->son[1]=x;<br /> }<br /> }<br /> x->son[w]=y;<br /> y->fa=x;<br /> update(y);<br /> update(x);<br /> }<br /> void splay(Node* x,Node* y){<br /> while(x->fa!=y){<br /> if(x->fa->fa==y){<br /> if(x==x->fa->son[0]){<br /> rotate(x,1);<br /> }else{<br /> rotate(x,0);<br /> }<br /> }else{<br /> if(x->fa==x->fa->fa->son[0]){<br /> if(x==x->fa->son[0]){<br /> rotate(x->fa,1);<br /> rotate(x,1);<br /> }else{<br /> rotate(x,0);<br /> rotate(x,1);<br /> }<br /> }else{<br /> if(x==x->fa->son[1]){<br /> rotate(x->fa,0);<br /> rotate(x,0);<br /> }else{<br /> rotate(x,1);<br /> rotate(x,0);<br /> }<br /> }<br /> }<br /> }<br /> if(y==null){<br /> root=x;<br /> }<br /> }<br /> void addNode(Node* x,Node* father,keyType val){<br /> x->key=val;<br /> x->fa=father;<br /> x->son[0]=x->son[1]=null;<br /> x->size=1;<br /> }<br /> void insert(keyType x){<br /> Node *y, *z;</p> <p> if(root==null){<br /> y=New();<br /> root=y;<br /> addNode(y,null,x);<br /> return;<br /> }</p> <p> y=root;<br /> do{<br /> y->size++;<br /> if(x<y->key){<br /> if(y->son[0]!=null){<br /> y=y->son[0];<br /> }else{<br /> z=New();<br /> addNode(z,y,x);<br /> y->son[0]=z;<br /> y=z;<br /> break;<br /> }<br /> }else{<br /> if(y->son[1]!=null){<br /> y=y->son[1];<br /> }else{<br /> z=New();<br /> addNode(z,y,x);<br /> y->son[1]=z;<br /> y=z;<br /> break;<br /> }<br /> }<br /> }while(true);<br /> splay(y,null);<br /> }<br /> Node* find(keyType x){<br /> Node* y;</p> <p> y=root;<br /> do{<br /> if(y->key==x){<br /> break;<br /> }<br /> if(x<y->key){<br /> if(y->son[0]==null){<br /> break;<br /> }else{<br /> y=y->son[0];<br /> }<br /> }else{<br /> if(y->son[1]==null){<br /> break;<br /> }else{<br /> y=y->son[1];<br /> }<br /> }<br /> }while(true);</p> <p> splay(y,null);<br /> return y;<br /> }<br /> bool exist(keyType x){<br /> Node* y;</p> <p> y=root;<br /> while(y!=null&&y->key!=x){<br /> if(x<y->key){<br /> y=y->son[0];<br /> }else{<br /> y=y->son[1];<br /> }<br /> }<br /> if(y!=null)<br /> splay(y,null);<br /> return y!=null;<br /> }<br /> void init(){<br /> nil.size=0;<br /> null=&nil;<br /> K=0;<br /> top=0;<br /> root=null;<br /> }<br /> void Delete(keyType x){<br /> Node *y, *z;</p> <p> y=find(x);<br /> splay(y,null);<br /> if(y->son[0]==null){<br /> if(y->son[1]==null){<br /> init();<br /> }else{<br /> root=y->son[1];<br /> y->son[1]->fa=null;<br /> }<br /> }else{<br /> z=y->son[0];<br /> while(z->son[1]!=null)<br /> z=z->son[1];<br /> splay(z,y);<br /> z->son[1]=y->son[1];<br /> if(y->son[1]!=null){<br /> y->son[1]->fa=z;<br /> };<br /> z->fa=null;<br /> root=z;<br /> update(z);<br /> }<br /> }<br /> keyType selete(int x){<br /> Node* y;</p> <p> y=root;<br /> while(1){<br /> if(x<=y->son[0]->size){<br /> y=y->son[0];<br /> }else{<br /> if(x==y->son[0]->size+1){<br /> break;<br /> }else{<br /> x=x-y->son[0]->size-1;<br /> y=y->son[1];<br /> }<br /> }<br /> }</p> <p> splay(y,null);<br /> return y->key;<br /> }<br /> void deleteNums(keyType x){<br /> Node* y;</p> <p> if(root==null){<br /> return;<br /> }<br /> y=find(x);<br /> splay(y,null);<br /> y->son[1]=null;<br /> if(y->key>=x){<br /> if(y->son[0]==null){<br /> init();<br /> }else{<br /> root=y->son[0];<br /> y->son[0]->fa=null;<br /> }<br /> }<br /> }<br /> int rank(keyType x){<br /> Node* y;</p> <p> if(root==null){<br /> return 0;<br /> }</p> <p> y=find(x);<br /> splay(y,null);<br /> return y->son[0]->size+(int)(y->key<=x);<br /> }<br /> keyType maxSmall(keyType x){<br /> Node* y;</p> <p> if(root==null){<br /> return -oo;<br /> }<br /> y=find(x);<br /> splay(y,null);<br /> if(y->key>x){<br /> y=y->son[0];<br /> if(y==null){<br /> return -oo;<br /> }<br /> while(y->son[1]!=null){<br /> y=y->son[1];<br /> }<br /> }<br /> return y->key;<br /> }<br /> keyType minBig(keyType x){<br /> Node* y;</p> <p> if(root==null){<br /> return oo;<br /> }<br /> y=find(x);<br /> splay(y,null);<br /> if(y->key<x){<br /> y=y->son[1];<br /> if(y==null){<br /> return oo;<br /> }<br /> while(y->son[0]!=null){<br /> y=y->son[0];<br /> }<br /> }<br /> return y->key;<br /> }<br /> int cnt,ret;<br /> void run(int x){<br /> int t1,t2;</p> <p> t1=minBig(x);<br /> t2=maxSmall(x);<br /> if(t1==oo){<br /> ret=(ret+abs(x-t2))%mod;<br /> Delete(t2);<br /> cnt--;<br /> }<br /> else if(t2==-oo){<br /> ret=(ret+abs(x-t1))%mod;<br /> Delete(t1);<br /> cnt--;<br /> }<br /> else if(abs(x-t1)<abs(x-t2)){<br /> ret=(ret+abs(x-t1))%mod;<br /> Delete(t1);<br /> cnt--;<br /> }<br /> else if(abs(x-t1)==abs(x-t2)){<br /> if(t1<t2){<br /> ret=(ret+abs(x-t1))%mod;<br /> Delete(t1);<br /> cnt--;<br /> }else{<br /> ret=(ret+abs(x-t2))%mod;<br /> Delete(t2);<br /> cnt--;<br /> }<br /> }else{<br /> ret=(ret+abs(x-t2))%mod;<br /> Delete(t2);<br /> cnt--;<br /> }<br /> }<br /> int main(){<br /> int n;<br /> int x,op;<br /> int type;</p> <p> while(~scanf("%d",&n)){<br /> init();<br /> type=-1;<br /> cnt=0;<br /> ret=0;<br /> for(int i=0;i<n;i++){<br /> scanf("%d%d",&op,&x);<br /> if(type==-1||type==op){<br /> type=op;<br /> insert(x);<br /> cnt++;<br /> }else{<br /> run(x);<br /> if(!cnt){<br /> type=-1;<br /> }<br /> }<br /> }</p> <p> printf("%d/n",ret);<br /> }</p> <p> return 0;<br /> }<br />