[HNOI2004]宠物收养所

Description

最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。 每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整 数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生： 被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。 1． 被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。 （任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点 值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。 2． 收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养 者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。 一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。 【任务描述】 你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也 没有领养者。

Input

第一行为一个正整数n，n<=80000，表示一年当中来到 收养所的宠物和领养者的总数。接下来的n行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数a, b，其中a=0表示宠物，a=1表示领养者，b表示宠物的特点值或是领养者希望领养宠物的特点值。（同一时间呆在收养所中的，要么全是宠物，要么全是领养 者，这些宠物和领养者的个数不会超过10000个）

Output

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和mod 1000000以后的结果。

 

 

 

 

 

 

Splay解法+疯狂的暴力对拍

 

 

建立两棵伸展树，一棵放宠物，一棵放领养者，可知任意时刻两棵树必有一棵为空树。

删除时比较麻烦，要考虑是否存在pre和next.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<fstream>
using namespace std;
//ifstream fin("fin.in");
//ofstream fout("test.out");

long long n,ans=0;
typedef struct{
    int tot,root,key[100000],pre[100000],ch[100000][2];
    }Node;
Node N[2];

void Newnode(int k,int &num,int father,int d){
    num=++N[k].tot;N[k].key[num]=d;N[k].pre[num]=father;
    N[k].ch[num][0]=N[k].ch[num][1]=0;return ;
    }

void Rotate(int k,int x,int kind){
    int y=N[k].pre[x];
    N[k].ch[y][!kind]=N[k].ch[x][kind];
    N[k].pre[N[k].ch[y][!kind]]=y;
    
    if(N[k].pre[y]) N[k].ch[N[k].pre[y]][y==N[k].ch[N[k].pre[y]][1]]=x;
    N[k].pre[x]=N[k].pre[y];
    
    
    N[k].pre[y]=x;
    N[k].ch[x][kind]=y;
    
    return ;
    }

void Splay(int k,int x,int goal){
    while(N[k].pre[x]!=goal)
    {
        int y=N[k].pre[x];
        if(N[k].pre[y]==goal) Rotate(k,x,N[k].ch[y][0]==x);
        else 
        {
            int z=N[k].pre[y];int kind=N[k].ch[z][0]==y;
            if(N[k].ch[y][!kind]==x) {Rotate(k,y,kind);Rotate(k,x,kind);}
            else {Rotate(k,x,!kind);Rotate(k,x,kind);}
            }
        }
    N[k].root=x;return ;
    
    }

int Insert(int k,int d){//return 1 则找到相等于d的节点 
    if(N[k].root==0) {Newnode(k,N[k].root,0,d);return 0;}//
    int x=N[k].root;
    while(N[k].ch[x][N[k].key[x]<d])
    {
        if(N[k].key[x]==d) {Splay(k,x,0);return 1;}
        x=N[k].ch[x][N[k].key[x]<d];
        }
    if(N[k].key[x]==d) {Splay(k,x,0);return 1;}
    
    Newnode(k,N[k].ch[x][N[k].key[x]<d],x,d);
    Splay(k,N[k].ch[x][N[k].key[x]<d],0);
    return 0;
    }

int Pre(int k,int root){
    if(N[k].ch[root][0]==0) return 0;
    int x=N[k].ch[root][0];
    while(N[k].ch[x][1])
    x=N[k].ch[x][1];
    return x;
    }

int Next(int k,int root){
    if(N[k].ch[root][1]==0) return 0;
    int x=N[k].ch[root][1];
    while(N[k].ch[x][0])
    x=N[k].ch[x][0];
    return x;
    }


int a,b;
void Change(int k,int c){             //删除root，splay c 
    int y=N[k].ch[N[k].root][1];
    N[k].ch[a][1]=y;
    N[k].pre[y]=a;
                
    N[k].root=N[k].ch[N[k].root][0];
    N[k].pre[N[k].root]=0;
    
    Splay(k,c,0);
    }
int Union(int k,int d){//合并root的两子树，并求值 
    a=Pre(k,N[k].root);
    b=Next(k,N[k].root);
    
    //cout<<N[k]
    
  //  cout<<"pre  "<<N[k].key[a]<<endl;
   // cout<<"next  "<<N[k].key[b]<<endl;
    if(a==0) 
    {
        ans+=abs(N[k].key[b]-d);ans%=1000000;
    //    N[k].ch[N[k].pre[b]][N[k].key[N[k].pre[b]]<N[k].key[b]]=0;
        N[k].root=N[k].ch[N[k].root][1];
        N[k].pre[N[k].root]=0;
        Splay(k,b,0);
        N[k].root=N[k].ch[N[k].root][1];
        N[k].pre[N[k].root]=0;
        return 0;
        }
    else if(b==0)
    {
        ans+=abs(N[k].key[a]-d);ans%=1000000;
        //N[k].ch[N[k].pre[a]][N[k].key[N[k].pre[a]]<N[k].key[a]]=0;
        N[k].root=N[k].ch[N[k].root][0];
        N[k].pre[N[k].root]=0;
        Splay(k,a,0);
        N[k].root=N[k].ch[N[k].root][0];
        N[k].pre[N[k].root]=0;
        return 0;
        } 
    else
    {
        ans+=min(abs(N[k].key[a]-d),abs(N[k].key[b]-d));ans%=1000000;
        if((abs(N[k].key[a]-d)==abs(N[k].key[b]-d)&&N[k].key[a]<N[k].key[b])||abs(N[k].key[a]-d)<abs(N[k].key[b]-d))
        {Change(k,a);return 1;}///splay a,删除a 
        else {Change(k,b);return 1;}
            } 
    }

void Print(int k,int x){
    cout<<N[k].key[x]<<"   "<<N[k].key[N[k].pre[x]]<<endl;
    if(N[k].ch[x][0]) Print(k,N[k].ch[x][0]);
    if(N[k].ch[x][1]) Print(k,N[k].ch[x][1]);
    }

void Delete(int k,int d){
    if(Insert(k,d))
    {
        a=Pre(k,N[k].root);
        if(a==0) 
        {
            N[k].root=N[k].ch[N[k].root][1];
            N[k].pre[N[k].root]=0;
            }
        else 
            Change(k,a);
        
        return ;
        }
    
//    cout<<"k  "<<k<<"   "<<d<<endl;
//    Print(k,N[k].root);
//    
    if(Union(k,d)) 
    {
        a=Pre(k,N[k].root);
        if(a==0) 
        {
            N[k].root=N[k].ch[N[k].root][1];
            N[k].pre[N[k].root]=0;
            }
        else 
            Change(k,a);
        }
//cout<<ans<<"  ans"<<endl;
    } 

int main()
{
    cin>>n;
    N[0].tot=N[1].tot=N[0].root=N[1].root=0;
    
    for(int i=1;i<=n;++i)
    {
        int x,y;
        cin>>x>>y;
        
        if(x==0) {if(N[1].root==0) Insert(0,y);else Delete(1,y);}
        if(x==1) {if(N[0].root==0) Insert(1,y);else {Delete(0,y);}}//Print(0,N[0].root);
//    cout<<N[0].root<<"  "<<N[1].root<<endl;  
    //    cout<<ans<<endl;                                         
        }
    
    cout<<ans<<endl;
//    system("pause");
    return 0;
    
    }