BZOJ1208_宠物收养所_KEY

题目传送门

平衡树的题。

因为题目给出条件（其实自己也知道）：同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过10000个。

所以只要维护一颗平衡树，它的里面要不全是人，要不全是宠物。

找到人的前驱后继比较。

code：

/**************************************************************

    Problem: 1208

    User: yekehe

    Language: C++

    Result: Accepted

    Time:180 ms

    Memory:2388 kb

****************************************************************/

#include <cstdio>

#include <cstdlib>

using namespace std;

int read()

{

    char c;while(c=getchar(),c<''||c>'');

    int x=c-'';while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x;

}

int N,now,root,cnt,dist;

int tr[][],v[],r[],f[];

void clear(int x){f[x]=tr[x][]=tr[x][]=r[x]=v[x]=;}

void up(int x){f[x]=f[tr[x][]]+f[tr[x][]];}

int abs(int x){return x>?x:-x;}

void rotate(int &x,int o)

{

    int k=tr[x][o];

    tr[x][o]=tr[k][o^];

    tr[k][o^]=x;

    f[k]=f[x];

    up(x);

    x=k;

}

void insert(int &x,int val)

{

    if(!x){

        x=++cnt;

        v[x]=val;

        r[x]=rand();

        f[x]++;

        return ;

    }

    int to=val>v[x];

    insert(tr[x][to],val);

    if(r[x]>r[tr[x][to]])rotate(x,to);

    return ;

}

void del(int &x,int val)

{

    if(v[x]==val){

        if(!(tr[x][]+tr[x][])){

            clear(x);x=;

            return ;

        }

        if(!(tr[x][]*tr[x][])){

            int w=tr[x][]+tr[x][];

            clear(x);x=w;

            return ;

        }

        rotate(x,);

        del(x,val);

        return ;

    }

    f[x]--;

    int to=val>v[x];

    del(tr[x][to],val);

    up(x);

    return ;

}

void pre(int x,int val)//前驱

{

    if(!x)return ;

    if(v[x]>=val)pre(tr[x][],val);

    else{

        dist=x;

        pre(tr[x][],val);

    }

}

void bac(int x,int val)//后继

{

    if(!x)return ;

    if(v[x]<=val)bac(tr[x][],val);

    else{

        dist=x;

        bac(tr[x][],val);

    }

}

int main()

{

    srand();

    N=read();

    int i,ans=,o1,o2,tot=;

        for(i=;i<=N;i++){

            int x=read(),y=read();

            if(!tot){insert(root,y),now=x;tot++;continue;}

            if(now==x)insert(root,y),tot++;

            else{

                dist=;pre(root,y);o1=dist;

                dist=;bac(root,y);o2=dist;

                if(!o1&&!o2)continue;

                int k1=o1?y-v[o1]:2e9,k2=o2?v[o2]-y:2e9;

                dist=k1>k2?o2:o1;//找较接近的值

                ans=(ans+abs(v[dist]-y))%;

                del(root,v[dist]);

                tot--;

            }

        }

    printf("%d",ans);

    return ;

}