BZOJ 1208 宠物收养所（splay入门题）

1208: [HNOI2004]宠物收养所

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 9802 Solved: 3926
[Submit][Status][Discuss]
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以后的结果。

Sample Input

0 2

0 4

1 3

1 2

1 5

Sample Output

(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)

题目链接：BZOJ 1208
splay入门题，只要找前驱和后继即可，主要用的操作是splay上的插入、删除，找前驱和后继操作，代码是参考大牛hzwer的
代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 80010;
const int mod = 1000000;
struct node
{
    int ch[2], v, f;
    void init()
    {
        ch[0] = ch[1] = 0;
    }
} T[N];
int rt, sz, pp, sp;

void init()
{
    rt = sz = 0;
}
inline int getson(int x)
{
    return T[T[x].f].ch[1] == x;
}
void rotate(int x, int &k)
{
    int f = T[x].f, ff = T[f].f, l = getson(x), r = l ^ 1;
    if (f == k)
        k = x;
    else
        T[ff].ch[getson(f)] = x;
    T[x].f = ff;
    T[f].ch[l] = T[x].ch[r];
    if (T[x].ch[r])
        T[T[x].ch[r]].f = f;
    T[x].ch[r] = f;
    T[f].f = x;
}
void splay(int x, int &k)
{
    while (x != k)
    {
        int f = T[x].f;
        if (f != k)
        {
            if (getson(f)^getson(x))
                rotate(x, k);
            else
                rotate(f, k);
        }
        rotate(x, k);
    }
}
void ins(int &k, int f, int v)
{
    if (!k)
    {
        T[k = ++sz].init();
        T[k].f = f;
        T[k].v = v;
        splay(k, rt);
    }
    else if (v < T[k].v)
        ins(T[k].ch[0], k, v);
    else
        ins(T[k].ch[1], k, v);
}
void getpre(int k, int v)
{
    if (!k)
        return ;
    if (v >= T[k].v)
    {
        pp = k;
        getpre(T[k].ch[1], v);
    }
    else
        getpre(T[k].ch[0], v);
}
void getsuc(int k, int v)
{
    if (!k)
        return ;
    if (v <= T[k].v)
    {
        sp = k;
        getsuc(T[k].ch[0], v);
    }
    else
        getsuc(T[k].ch[1], v);
}
void del(int x)
{
    splay(x, rt);
    if (T[x].ch[0] * T[x].ch[1] == 0)
        rt = T[x].ch[0] + T[x].ch[1];
    else
    {
        int k = T[x].ch[1];
        while (T[k].ch[0])
            k = T[k].ch[0];
        T[k].ch[0] = T[x].ch[0];
        T[T[x].ch[0]].f = k;
        rt = T[x].ch[1];
    }
    T[rt].f = 0;
}
int main(void)
{
    int n, ops, i;
    while (~scanf("%d", &n))
    {
        init();
        int kind = -1, ans = 0;
        for (i = 0; i < n; ++i)
        {
            int v;
            scanf("%d%d", &ops, &v);
            if (!rt)
            {
                kind = ops;
                ins(rt, 0, v);
            }
            else if (kind == ops)
                ins(rt, 0, v);
            else
            {
                pp = sp = 0;
                getpre(rt, v);
                getsuc(rt, v);
                if (pp && sp)
                {
                    int pv = v - T[pp].v, sv = T[sp].v - v;
                    if (pv <= sv)
                    {
                        ans = (ans + pv) % mod;
                        del(pp);
                    }
                    else
                    {
                        ans = (ans + sv) % mod;
                        del(sp);
                    }
                }
                else if (pp)
                {
                    ans = (ans + v - T[pp].v) % mod;
                    del(pp);
                }
                else if (sp)
                {
                    ans = (ans + T[sp].v - v) % mod;
                    del(sp);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}