宠物收养所[Treap]

题目描述

凡凡开了一间宠物收养场。收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。

每个领养者都希望领养到自己满意的宠物，凡凡根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养场的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少。

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。

收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。

一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

输入输出格式

输入格式：

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

输出格式：

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

输入样例#1： 

5

0 2

0 4

1 3

1 2

1 5

输出样例#1： 

3

注：abs(3-2) + abs(2-4)=3，

最后一个领养者没有宠物可以领养。

分析

存一下当前是宠物多还是顾客多，随时在宠物和顾客之间转换

每一次加进来一个宠物时

如果是宠物树就直接插入

否则查找当前顾客的期望的前驱和后继（不是严格的）

拉出来删除，统计答案

#include<bits/stdc++.h>
#define N 40005
using namespace std;
struct Node{
    int ch[2],key,p,size,num;
}t[N];
int n,tot,sign,root,ans1,ans2,ans;//tot>0 则为狗多  
int read(){
    int cnt=0,f=1;char ch=0;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}
    while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();
    return cnt*f;
}
int randon(){
    static int seed=233;
    return seed=int(seed*47281LL%2147483647);
}
void update_size(int o){
    t[o].size=t[t[o].ch[0]].size+t[t[o].ch[1]].size+t[o].num;
}
void rotate(int &o,int type){
    int x=t[o].ch[type];
    t[o].ch[type]=t[x].ch[type^1];
    t[x].ch[type^1]=o;
    t[x].size=t[o].size;
    update_size(o);
    o=x;
}
void insert(int &o,int val){
    if(o==0){
        o=++tot;
        t[o].p=randon(),t[o].size=t[o].num=1,t[o].key=val;
        return;
    }
    if(t[o].key==val){
        t[o].num++;return;
    }
    if(val<t[o].key){
        insert(t[o].ch[0],val);
        if(t[t[o].ch[0]].p<t[o].p) 
            rotate(o,0);
    }
    else{
        insert(t[o].ch[1],val);
        if(t[t[o].ch[1]].p<t[o].p)
            rotate(o,1);
    }
}
void erase(int &o,int val){
    if(o==0) return;
    if(t[o].key==val){
        if(t[o].num>1){
            t[o].num--,t[o].size--;return;
        }
        else{
            if(t[o].ch[0]==0) o=t[o].ch[1];
            else if(t[o].ch[1]==0) o=t[o].ch[0];
            else{
                if(t[t[o].ch[0]].p<t[t[o].ch[1]].p)
                    rotate(o,0),erase(o,val);
                else rotate(o,1),erase(o,val);
            }
        }
        return;
    }
    if(val<t[o].key) t[o].size--,erase(t[o].ch[0],val);
    else t[o].size--,erase(t[o].ch[1],val);
}
void pre(int o,int val){
    if(o==0) return;
    if(val>=t[o].key){
        ans1=o,pre(t[o].ch[1],val);
    }
    else pre(t[o].ch[0],val);
}
void suf(int o,int val){
    if(o==0) return;
    if(val<=t[o].key){
        ans2=o,suf(t[o].ch[0],val);
    }
    else suf(t[o].ch[1],val);
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int op=read(),x=read();//0是狗
        ans1=0,ans2=0;
        if(sign>0){
            if(op==0) insert(root,x);
            else{//人来找狗,(找x的前驱后继) 
                pre(root,x),suf(root,x);
                int x1=x-t[ans1].key;
                int x2=t[ans2].key-x;
                if(ans1==0&&ans2==0) continue;
                if(ans1==0){ans+=x2,erase(root,t[ans2].key);}
                else if(ans2==0){ans+=x1,erase(root,t[ans1].key);}
                else if(x1<=x2){ans+=x1,erase(root,t[ans1].key);}
                else{ans+=x2,erase(root,t[ans2].key);}
                //删除找到的点
            } 
        } 
        else if(sign==0) insert(root,x);
        else{
            if(op==0){//狗找人,(找x的前驱后继) 
                pre(root,x),suf(root,x);
                int x1=x-t[ans1].key;
                int x2=t[ans2].key-x;
                if(ans1==0&&ans2==0) continue;
                if(ans1==0){ans+=x2,erase(root,t[ans2].key);}
                else if(ans2==0){ans+=x1,erase(root,t[ans1].key);}
                else if(x1<=x2){ans+=x1,erase(root,t[ans1].key);}
                else{ans+=x2,erase(root,t[ans2].key);}
            }
            else insert(root,x); 
        }
        sign+=(op==0?1:-1);
    }cout<<ans;
    return 0;
}