题目链接：

题意：

　　有一个宠物收养所，在接下来一段时间内会陆续有一些宠物进到店里，或是一些人来领养宠物。宠物和人的总数量为n。

　　t = 0代表宠物，t = 1代表人。

　　宠物和人分别有一个特点值a和b。有两种情况：

　　　　（1）店里全是宠物，这时进来一个人来领养宠物。那么他会领养走abs(a-b)最小的那只宠物（b = a - x or a + x）。

　　　　　　如果使得abs(a-b)最小的有不止一只宠物，那么b = a - x的那只会被领养走。

　　　　（2）店里全是等待的人。这事有一只宠物被送进店里，那么它会被abs(a-b)最小的那个人领养走（a = b - x or b + x）。

　　　　　　如果使得abs(a-b)最小的不只有一个人，那么宠物会被a = b - x的人领养走。

　　按照依次来到店里的顺序，给出a,b。

　　a = 0代表宠物，a = 1代表人。b为对应的特点值。

　　定义每一次领养的不满意度 = abs（宠物特点值 - 人的特点值）

　　问你所有不满意度之和 MOD 1000000。

 

题解：

　　Splay。

 

　　分析：

　　　　（1）在每一个时刻（除了正在领养），店里要么全是宠物，要么全是人，要么为空。

　　　　（2）在本题中，除了只能是人和宠物匹配这个特性，人和宠物是等价的，都可以在店里等待。

　　　　（3）有可能先进来一大堆宠物，再进来一大堆人。这时搜索树会退化成链，所以要用splay。

 

　　实现：

　　　　每输入一对a,b:

　　　　（1）如果店为空，那么将东西加入树中，并将树的类型改为a。

　　　　（2）如果进来一个同类，那么将当前东西加入树中。

　　　　（3）如果进来一个异类，那么找出对于这个异类的特点值的前驱pre与后继suc（类型均为pair<int,int>(dif,idx)）。

　　　　　　将被删除的东西为res = min(pre,suc)。

　　　　　　所以erase(res.second)，并更新答案ans = (ans + res.first) % MOD。

 

AC Code:

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #define MAX_N 80005  5 #define MOD 1000000  6 #define INF 100000000  7   8 using namespace std;  9  10 int n,a,b; 11 int ans=0; 12 int type; 13 int siz=0; 14 int tot=0; 15 int root=-1; 16 int dat[MAX_N]; 17 int par[MAX_N]; 18 int lson[MAX_N]; 19 int rson[MAX_N]; 20  21 void rotate(int x,int type,int *lson,int *rson) 22 { 23     if(type==1) swap(lson,rson); 24     int y=par[x]; 25     int z=par[y]; 26     lson[y]=rson[x]; 27     if(rson[x]!=-1) par[rson[x]]=y; 28     par[x]=z; 29     if(z!=-1) 30     { 31         if(lson[z]==y) lson[z]=x; 32         else rson[z]=x; 33     } 34     rson[x]=y; 35     par[y]=x; 36 } 37  38 void splay(int x,int act) 39 { 40     while(par[x]!=act) 41     { 42         int y=par[x]; 43         int z=par[y]; 44         if(z==act) 45         { 46             if(lson[y]==x) rotate(x,0,lson,rson); 47             else rotate(x,1,lson,rson); 48         } 49         else 50         { 51             if(lson[z]==y && lson[y]==x) 52             { 53                 rotate(y,0,lson,rson); 54                 rotate(x,0,lson,rson); 55             } 56             if(rson[z]==y && rson[y]==x) 57             { 58                 rotate(y,1,lson,rson); 59                 rotate(x,1,lson,rson); 60             } 61             if(rson[z]==y && lson[y]==x) 62             { 63                 rotate(x,0,lson,rson); 64                 rotate(x,1,lson,rson); 65             } 66             if(lson[z]==y && rson[y]==x) 67             { 68                 rotate(x,1,lson,rson); 69                 rotate(x,0,lson,rson); 70             } 71         } 72     } 73     if(act==-1) root=x; 74 } 75  76 int find(int val) 77 { 78     int now=root; 79     while(now!=-1) 80     { 81         if(val==dat[now]) return now; 82         if(val
        
         dat[now]) now=rson[now]; 84     } 85     return -1; 86 } 87  88 void new_node(int val,int p,int &kid) 89 { 90     dat[tot]=val; 91     par[tot]=p; 92     lson[tot]=-1; 93     rson[tot]=-1; 94     kid=tot; 95     splay(tot,-1); 96     tot++; 97 } 98  99 void insert(int val)100 {101     siz++;102     if(root==-1)103     {104         int temp;105         root=tot;106         new_node(val,-1,temp);107         return;108     }109     int now=root;110     while(1)111     {112         if(val==dat[now]) return;113         if(val
         
          dat[now])123         {124             if(rson[now]==-1)125             {126                 new_node(val,now,rson[now]);127                 return;128             }129             else now=rson[now];130         }131     }132 }133 134 void erase(int x)135 {136     siz--;137     splay(x,-1);138     if(lson[x]==-1 && rson[x]==-1)139     {140         root=-1;141         return;142     }143     if(lson[x]==-1)144     {145         root=rson[x];146         par[rson[x]]=-1;147         return;148     }149     if(rson[x]==-1)150     {151         root=lson[x];152         par[lson[x]]=-1;153         return;154     }155     int pre=lson[root];156     while(rson[pre]!=-1) pre=rson[pre];157     splay(pre,x);158     par[pre]=-1;159     rson[pre]=rson[x];160     par[rson[x]]=pre;161     root=pre;162 }163 164 pair
          
            precursor(int val)165 {166 int now=root;167 int pre=-1;168 int dif=INF;169 while(now!=-1)170 {171 if(dat[now]
           
            val) now=lson[now];177 else now=rson[now];178 }179 return pair
            
             (dif,pre);180 }181 182 pair
             
               succeed(int val)183 {184 int now=root;185 int suc=-1;186 int dif=INF;187 while(now!=-1)188 {189 if(dat[now]>val && dat[now]-val
              
               val) now=lson[now];195 else now=rson[now];196 }197 return pair
               
                (dif,suc);198 }199 200 int main()201 {202 cin>>n;203 for(int i=0;i
                
                 >a>>b;206 if(siz==0)207 {208 insert(b);209 type=a;210 }211 else212 {213 if(a==type) insert(b);214 else215 {216 pair
                 
                   pre=precursor(b);217 pair
                  
                    suc=succeed(b);218 pair
                   
                     res=min(pre,suc);219 erase(res.second);220 ans=(ans+res.first)%MOD;221 }222 }223 }224 cout<
                    
                     <