647
NHOI 2004 寵物收養所 splay解法
1208: [HNOI2004]寵物收養所
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3047 Solved: 1098
[Submit][Status]
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，最後一個領養者沒有寵物可以領養)
HINT
Source
[Submit][Status] 刪掉節點，每次都把節點的前驅轉到根，把後繼轉到根的子節點，這樣要刪的點就是根的右兒子的左兒子，直接刪掉就行了。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=10005;
const int oo=2e9;
struct SplayTree
{
int son[mm][2],far[mm],val[mm],sum[mm];
int rt,size;
void PushUp(int x)
{
sum[x]=sum[son[x][0]]+sum[son[x][1]]+1;
}
void Link(int x,int y,int c)
{
far[x]=y,son[y][c]=x;
}
void Rotate(int x,int c)
{
int y=far[x];
Link(x,far[y],son[far[y]][1]==y);
Link(son[x][!c],y,c);
Link(y,x,!c);
PushUp(y);
}
void Splay(int x,int g)
{
for(; far[x]!=g;)
{
int y=far[x],cx=(son[y][1]==x),cy=(son[far[y]][1]==y);
if(far[y]==g)Rotate(x,cx);
else
{
if(cx==cy)Rotate(y,cy);
else Rotate(x,cx);
Rotate(x,cy);
}
}
PushUp(x);
if(!g)rt=x;
}
void NewNode(int y,int &x,int a)
{
x=++size;
far[x]=y,val[x]=a,sum[x]=1;
son[x][0]=son[x][1]=0;
}
void Insert(int a)
{
int x=rt;
while(son[x][val[x]<a])x=son[x][val[x]<a];
NewNode(x,son[x][val[x]<a],a);
Splay(size,0);
}
void Prepare()
{
memset(sum,0,sizeof(sum));
NewNode(size=0,rt,-oo);
NewNode(rt,son[rt][1],oo);
sum[rt]=2;
}
int Suc(int a)
{
int x=rt,ret=oo;
while(x)
{
if(val[x]==a) return a;
if(val[x]>a) ret=min(ret,val[x]);
x=son[x][val[x]<a];
}
return ret;
}
int Pre(int a)
{
int x=rt,ret=-oo;
while(x)
{
if(val[x]==a)return a;
if(val[x]<a)ret=max(ret,val[x]);
x=son[x][val[x]<a];
}
return ret;
}
int Find(int a)
{
int x=rt,ans=0;
while(x)
{
if(val[x]==a) ans=x;
x=son[x][val[x]<a];
}
return ans;
}
void Select(int k,int g)
{
int x=rt;
sum[0]=0;
while(sum[son[x][0]]+1!=k)
{
if(sum[son[x][0]]+1>k) x=son[x][0];
else k-=(sum[son[x][0]]+1),x=son[x][1];
}
Splay(x,g);
}
void Delete(int a)
{
int x=Find(a);
Splay(x,0);
int y=sum[son[x][0]];
Select(y,0);
Select(y+2,rt);
son[son[rt][1]][0]=0;
PushUp(son[rt][1]);
PushUp(rt);
size--;
}
void display(int x)
{
if(x==0)
return;
display(son[x][0]);
cout<<"now: "<<x<<" "<<val[x]<<" sum: "<<sum[x]<<" ls: "<<son[x][0]<<" rs: "<<son[x][1]<<endl;
display(son[x][1]);
}
} spt;
int main()
{
int n,a,b,ans,f;
while(~scanf("%d",&n))
{
ans=0;
spt.Prepare();
int size=0;
for(int i=0; i<n; i++)
{
scanf("%d%d",&a,&b);
if(size==0||a==f)
size++,spt.Insert(b),f=a;
else
{
int p=spt.Pre(b),q=spt.Suc(b);
if(b-p<=q-b)ans+=b-p,spt.Delete(p);
else ans+=q-b,spt.Delete(q);
if(ans>=1000000)ans%=1000000;
size--;
}
}
printf("%d\n",ans);
}
return 0;
}
最後更新：2017-04-03 16:48:59