|
【HNOI2004】宠物收养所 |
Time Limit:10000MS Memory Limit:65536K
Total Submit:248 Accepted:157
Case Time Limit:1000MS
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
5
0 2
0 4
1 3
1 2
1 5
Sample Output
3
Hint
样例说明：样例的计算方法：(abs(3-2) + abs(2-4)=3，最后一个领养者没有宠物可以领养)
Source
xinyue
在找前驱和后继的时候，可能出现前驱和后继不存在，应当返回inf。。
由于一棵树，要么为空，要么全为宠物或者全为人，加一个标记，表示树内现在的种类，对于一个新进来的，判断是否一致，一致则插入，否则找出一个相邻的删掉。
用splay tree写的，TLE，请路过的大牛指点。。。。。
ins（）插入；
Romove（），删除任意值的节点
find（）找到任意值的节点号
Get_pre（）找到k值的前驱；
Get_next（）找到k值的后驱
Inorder（）中序遍历
TLE代码（插入，删除某个值的节点，）：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 1<<31
#define ll long long
#define mod 1000000
#define N 20010
#define Key_value ch[ch[root][1]][0]
using namespace std;
int key[N],n,m;
int pre[N];
int ch[N][2],tot,root,node[N];
int size[N];
void newnode(int &r,int k,int fa)
{
r=++tot;
ch[r][0]=ch[r][1]=0;
key[r]=k;
pre[r]=fa;
size[r]=1;
}
void push_up(int r){
size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
}
void Rotate(int x,int kind)
{
int y=pre[x];
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if(pre[y])
ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
push_up(y);
}
void splay(int r,int goal)
{
while(pre[r]!=goal)
{
if(pre[pre[r]]==goal)
Rotate(r,ch[pre[r]][0]==r);
else
{
int y=pre[r];
int kind=(ch[pre[y]][0]==y);
if(ch[y][kind]==r)
{
Rotate(r,!kind);
Rotate(r,kind);
}
else
{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
push_up(r);
if(goal==0)
root=r;
}
void RotateTo(int k,int goal)
{
int r=root;
while(size[ch[r][0]]!=k)
{
if(k<size[ch[r][0]])
r=ch[r][0];
else
{
k-=(size[ch[r][0]]+1);
r=ch[r][1];
}
}
splay(r,goal);
}
inline int ins(int &x,int data,int fa)
{
if(x==0)
{
newnode(x,data,fa);
}
else
{
size[x]++;
ins(ch[x][key[x]<data],data,x);
splay(ch[x][key[x]<data],0);
}
return 1;
}
int Get_Min(int r){
while(ch[r][0]){
r=ch[r][0];
}
return r;
}
int Get_Max(int r){
while(ch[r][1]){
r=ch[r][1];
}
return r;
}
int Get_pre(int &r,int y,int k)
{
if(r==0)
{
if(y==0)
return inf;
return key[y];
}
if(k>=key[r])return Get_pre(ch[r][1],r,k);
else
return Get_pre(ch[r][0],y,k);
}
int Get_next(int &r,int y,int k)
{
if(r==0)
{
if(y==0)
{
return inf;
}
return key[y];
}
if(k<=key[r])
{
return Get_next(ch[r][0],r,k);
}
else
{
return Get_next(ch[r][1],y,k);
}
}
int find(int r,int k)
{
if(!r)return 0;
if(key[r]==k)return r;
if(key[r]<k)return find(ch[r][1],k);
return find(ch[r][0],k);
}
void Remove(int c)
{
int k=find(root,c);
splay(k,0);
if(size[root]==1)
{
root==0;
pre[root]=0;
size[root]=0;
ch[root][0]=ch[root][1]=0;
}
else
{
int y=Get_Min(ch[root][1]);
splay(y,root);
pre[ch[root][0]]=ch[root][1];
Key_value=ch[root][0];
root=ch[root][1];
push_up(root);
}
}
void Inorder(int &r){
printf("r=%d\n",r);
if(r==0) return;
Inorder(ch[r][0]);
printf("%d\n",key[r]);
Inorder(ch[r][1]);
}
int main() {
int k;
ll ans;
int kind,treekind;
scanf("%d",&n);
tot=root=0;ans=0;m=0;
for(int i=0;i<n;i++)
{
scanf("%d%d",&kind,&k);
if(m==0||kind^treekind==0)
{
treekind=kind;
ins(root,k,0);
m++;
}
else
if(kind^treekind==1)
{
int a=Get_pre(root,0,k);
int b=Get_next(root,0,k);
if(abs(a-k)<=abs(b-k)){
ans=(ans+abs(a-k))%mod;
Remove(a);
}
else
{
ans=(ans+abs(b-k))%mod;
Remove(b);
}
m--;
}
}
printf("%I64d\n",ans);
return 0;
}