最近，阿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)。【任务描述】你得到了一年 当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。
刚看了SBT于是就用SBT写了，记录当前SBT中是人还是狗，每次判断相同的话就加入树中，不同找前驱和后驱，绝对值最小的删除点，更新答案。
前驱后驱写的时候凌乱了调了好久ORZ
/**************************************************************
Problem: 1208
User: 1115825064
Language: C++
Result: Accepted
Time:260 ms
Memory:2528 kb
****************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int N=80010,mod=1000000;
struct T{
int l,r,size,w;
}tr[N];
int n,now,lai,top;
int root;
long long ans=0;
void left_rot(int &x)
{
int y=tr[x].r;
tr[x].r=tr[y].l;
tr[y].l=x;
tr[y].size=tr[x].size;
tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+1;
x=y;
}
void right_rot(int &x)
{
int y=tr[x].l;
tr[x].l=tr[y].r;
tr[y].r=x;
tr[y].size=tr[x].size;
tr[x].size=tr[tr[x].l].size+tr[tr[x].r].size+1;
x=y;
}
void maintain(int &x,bool flag)
{
if(!flag)
{
if(tr[tr[tr[x].l].l].size>tr[tr[x].r].size)
right_rot(x);
else if(tr[tr[tr[x].l].r].size>tr[tr[x].r].size)
{
left_rot(tr[x].l);
right_rot(x);
}
else return ;
}
else
{
if(tr[tr[tr[x].r].r].size>tr[tr[x].l].size)
left_rot(x);
else if(tr[tr[tr[x].r].l].size>tr[tr[x].l].size)
{
right_rot(tr[x].r);
left_rot(x);
}
else return ;
}
maintain(tr[x].l,0);
maintain(tr[x].r,1);
maintain(x,0);
maintain(x,1);
}
void insert(int &x,int k)
{
if(x==0)
{
x=++top;
tr[x].l=tr[x].r=0;
tr[x].size=1;
tr[x].w=k;
}
else
{
tr[x].size++;
if(k<tr[x].w) insert(tr[x].l,k);
else insert(tr[x].r,k);
maintain(x,k>tr[x].w);
}
}
int del(int &p,int w)
{
tr[p].size--;
if(w==tr[p].w||(tr[p].l==0&&w<tr[p].w)||tr[p].r==0&&w>tr[p].w)
{
int de=tr[p].w;
if(!tr[p].l||!tr[p].r)
{
p=tr[p].l+tr[p].r;
}
else
{
tr[p].w=del(tr[p].l,w);
}
return de;
}
if(w<tr[p].w) return del(tr[p].l,w);
else return del(tr[p].r,w);
}
int find_max(int &x,int y,int w)
{
if(x==0) return y;
if(tr[x].w>=w) return find_max(tr[x].l,x,w);
else return find_max(tr[x].r,y,w);
}
int find_min(int &x,int y,int w)
{
if(x==0) return y;
if(tr[x].w<=w) return find_min(tr[x].r,x,w);
else return find_min(tr[x].l,y,w);
}
int main()
{
// freopen("1.txt","r",stdin);
// freopen("2.out","w",stdout);
scanf("%d",&n);
while(n--)
{
int a,b;
scanf("%d%d",&a,&b);
if(!lai)
{
now=a;
insert(root,b);
lai++;
}
else
{
if(now==a)
{
lai++;
insert(root,b);
}
else
{
lai--;
int x1=find_min(root,0,b),
x2=find_max(root,0,b),
p1=b-tr[x1].w,
p2=tr[x2].w-b;
if(x2==0||(p1<=p2&&p1>=0&&x1!=0))
{
ans+=p1;
ans%=mod;
del(root,tr[x1].w);
}
if(x1==0||(p1>p2&&p2>=0&&x2!=0))
{
ans+=p2;
ans%=mod;
del(root,tr[x2].w);
}
}
}
//cout<<ans<<endl;
}
printf("%lld",ans);
return 0;
}
评论 (0)
