[平衡树][HNOI2004]宠物收养所

题目传送门：https://www.luogu.org/problemnew/show/P2286

----------

####问题描述
　　最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。
　　每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值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以后的结果。

----------
###题解：
省选出板题，emm，<del>挺好</del>
很明显，既然要求一个值与另一个值的最小差，那么我们很容易想到用平衡树求前驱后继。这道题只是在最裸的板上边加了一点变化。我们维护一颗Splay树。
假设现在插入一个动物。那么此时平衡树里只可能全是动物的特点值或者顾客的需求值（稍后解释）。如果还有顾客需要宠物，那么将这个动物的特点值插入Splay，求一次前驱后继，统计出最小代价，然后将这个特点值连带与他配对的顾客需求值一起从Splay里删除。这样操作相当于是把一个顾客与一个动物抵消了。所以，平衡树里不可能既存在特点值，有存在需求值。那么对于顾客的插入操作就同理了。
还有一种特殊情况就是需求值与特点值刚好相等。很简单，每次插入前询问当前是否存在这个值，如果存在，那就删除。因为相等，所以差为零，不对答案进行修改。
小细节就详见代码了。

----------

贴上代码:
```
#include<cstdio>
#include<cstdlib>
#define maxn 100005
using namespace std;
int ls[maxn],rs[maxn],val[maxn],fa[maxn],size[maxn];
int root,tot;
void rotr(int x)
{
    int y=fa[x],z=fa[y];
    if(ls[z]==y) ls[z]=x;
    else rs[z]=x;
    fa[x]=z;
    ls[y]=rs[x];
    fa[rs[x]]=y;
    rs[x]=y;
    fa[y]=x;
    size[x]=size[y];
    size[y]=size[ls[y]]+size[rs[y]]+1;
}
void rotl(int x)
{
    int y=fa[x],z=fa[y];
    if(ls[z]==y) ls[z]=x;
    else rs[z]=x;
    fa[x]=z;
    rs[y]=ls[x];
    fa[ls[x]]=y;
    ls[x]=y;
    fa[y]=x;
    size[x]=size[y];
    size[y]=size[ls[y]]+size[rs[y]]+1;
}
void splay(int x)
{
    int y,z;
    while(fa[x])
    {
        y=fa[x],z=fa[y];
        if(z)
        {
            if(ls[z]==y)
            {
                if(ls[y]==x) rotr(y),rotr(x);
                else rotl(x),rotr(x);
            }
            else
            {
                if(rs[y]==x) rotl(y),rotl(x);
                else rotr(x),rotl(x);
            }
        }
        else
        {
            if(ls[y]==x) rotr(x);
            else rotl(x);
        }
    }
    root=x;
}
int getmax(int k)
{
    int p=k;
    while(rs[p]) p=rs[p];
    return p;
}
void del(int p)
{
    splay(p);
    int l=ls[p],r=rs[p];
    ls[p]=rs[p]=fa[l]=fa[r]=0;
    if(!l) root=r,fa[r]=0;
    else
    {
        l=getmax(l);
        splay(l);
        fa[l]=0,fa[r]=l,rs[l]=r;
        size[root]+=size[rs[root]];
    }
}
int find(int x)
{
    int p=root;
    while(p)
    {
        if(x==val[p]) return p;
        if(x<val[p]) p=ls[p];
        else p=rs[p];
    }
    return p;
}
int findprev(int x)
{
    int p=ls[x];
    if(!p) return 0;
    while(rs[p]) p=rs[p];
    return p;
}
int findnext(int x)
{
    int p=rs[x];
    if(!p) return 0;
    while(ls[p]) p=ls[p];
    return p;
}
void insert(int k)
{
    if(!tot||!root)
    {
        val[++tot]=k;
        fa[tot]=0;
        size[tot]=1;
        root=tot;
        return;
    }
    tot++;
    int p=root;
    while(p)
    {
        size[p]++;
        if(k<val[p])
        {
            if(ls[p]) p=ls[p];
            else {ls[p]=tot;break;}
        }
        else
        {
            if(rs[p]) p=rs[p];
            else {rs[p]=tot;break;}
        }
    }
    val[tot]=k;
    fa[tot]=p;
    size[tot]=1;
    splay(tot);
}
int main()
{
    int n,acnt=0,ccnt=0,ans=0;//两个cnt维护顾客数与宠物数
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int cmd,a;
        scanf("%d%d",&cmd,&a);
        if(cmd==0)
        {
            if(ccnt!=0)
            {
                int pos=find(a);
                if(pos) {del(pos);continue;}
                insert(a);
                int lpos=findprev(root),rpos=findnext(root);
                if(lpos==0) del(rpos),ans+=val[rpos]-a;
                else if(rpos==0) del(lpos),ans+=a-val[lpos];
                else if(a-val[lpos]<=val[rpos]-a) del(lpos),ans+=a-val[lpos];
                else del(rpos),ans+=val[rpos]-a;
                ans%=1000000;
                del(find(a));
                ccnt--;
            }
            else insert(a),acnt++;//如果没有需求，直接插入
        }
        else
        {
            if(acnt!=0)
            {
                int pos=find(a);
                if(pos) {del(pos);continue;}
                insert(a);
                int lpos=findprev(root),rpos=findnext(root);
                if(lpos==0) del(rpos),ans+=val[rpos]-a;
                else if(rpos==0) del(lpos),ans+=a-val[lpos];
                else if(a-val[lpos]<=val[rpos]-a) del(lpos),ans+=a-val[lpos];
                else del(rpos),ans+=val[rpos]-a;
                ans%=1000000;
                del(find(a));
                acnt--;
            }
            else insert(a),ccnt++;
        }
    }
    printf("%d\n",ans%1000000);
}
```

PhantasmDragon 's Blog