1 #include
     
       2 #include
      
        3 using namespace std; 4 int n,size,rt,kind,t1,t2; 5 long long ans; 6 int tr[80001][2],num[80001],fa[80001]; 7 void rotate(int x,int &k) 8 { 9     int y=fa[x],z=fa[y],l,r;10     if(tr[y][0]==x)l=0;else l=1;r=l^1;11     if(y==k)k=x;12     else{
   if(tr[z][0]==y)tr[z][0]=x;else tr[z][1]=x;}13     fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;14     tr[y][l]=tr[x][r];tr[x][r]=y;15 }16 void splay(int x,int &k)17 {18     int y,z;19     while(x!=k)20     {21         y=fa[x],z=fa[y];22         if(y!=k)23         {24             if((tr[y][0]==x)^(tr[z][0]==y))rotate(x,k);25             else rotate(y,k);26         }27         rotate(x,k);28     }29 }30 void ins(int &k,int x,int last)31 {32     if(k==0){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}33     if(x
       
        =x){t2=k;ask_after(tr[k][0],x);}59     else ask_after(tr[k][1],x);60 }61   62 int main()63 {64     scanf("%d",&n);65     int f,x;66     for(int i=1;i<=n;i++)67     {68         scanf("%d%d",&f,&x);69         if(!rt){kind=f;}70         if(kind==f){ins(rt,x,0);71           }72         else73         {74             t1=t2=-1;75             ask_before(rt,x);ask_after(rt,x);76             if(t1==-1){ans+=num[t2]-x;ans%=1000000;del(t2);}77             else if(t2==-1){ans+=x-num[t1];ans%=1000000;del(t1);}78             else79             {80                 if(x-num[t1]>num[t2]-x)  {ans+=num[t2]-x;ans%=1000000;del(t2);}81                 else{ans+=x-num[t1];ans%=1000000;del(t1);}82             }83         }   84     }85     cout<
        
         <
        
       
      
     

平衡树，当宠物多时，将宠物加入平衡树中，当读入一个收养者时，找收养者值的前驱和后继，并把接近的删除。收养者多是也这样。