1208: [HNOI2004]寵物收養(yǎng)所

Time Limit: 10 Sec Memory Limit: 162 MB

    Submit: 5923 Solved: 2296

    [Submit][Status][Discuss]

Description

    最近，阿Q開了一間寵物收養(yǎng)所，

bzoj1208[HNOI2004]寵物收養(yǎng)所

。收養(yǎng)所提供兩種服務(wù)：收養(yǎng)被主人遺棄的寵物和讓新的主人領(lǐng)養(yǎng)這些寵物。每個領(lǐng)養(yǎng)者都希望領(lǐng)養(yǎng)到自己滿意的寵物，阿Q根據(jù)領(lǐng)養(yǎng)者的要求通過他自己發(fā)明的一個特殊的公式，得出該領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)的寵物的特點值a（a是一個正整數(shù)，a<2^31），而他也給每個處在收養(yǎng)所的寵物一個特點值。這樣他就能夠很方便的處理整個領(lǐng)養(yǎng)寵物的過程了，寵物收養(yǎng)所總是會有兩種情況發(fā)生：被遺棄的寵物過多或者是想要收養(yǎng)寵物的人太多，而寵物太少。 1． 被遺棄的寵物過多時，假若到來一個領(lǐng)養(yǎng)者，這個領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)的寵物的特點值為a，那么它將會領(lǐng)養(yǎng)一只目前未被領(lǐng)養(yǎng)的寵物中特點值最接近a的一只寵物。（任何兩只寵物的特點值都不可能是相同的，任何兩個領(lǐng)養(yǎng)者的希望領(lǐng)養(yǎng)寵物的特點值也不可能是一樣的）如果有兩只滿足要求的寵物，即存在兩只寵物他們的特點值分別為a-b和a+b，那么領(lǐng)養(yǎng)者將會領(lǐng)養(yǎng)特點值為a-b的那只寵物。 2． 收養(yǎng)寵物的人過多，假若到來一只被收養(yǎng)的寵物，那么哪個領(lǐng)養(yǎng)者能夠領(lǐng)養(yǎng)它呢？能夠領(lǐng)養(yǎng)它的領(lǐng)養(yǎng)者，是那個希望被領(lǐng)養(yǎng)寵物的特點值最接近該寵物特點值的領(lǐng)養(yǎng)者，如果該寵物的特點值為a，存在兩個領(lǐng)養(yǎng)者他們希望領(lǐng)養(yǎng)寵物的特點值分別為a-b和a+b，那么特點值為a-b的那個領(lǐng)養(yǎng)者將成功領(lǐng)養(yǎng)該寵物。 一個領(lǐng)養(yǎng)者領(lǐng)養(yǎng)了一個特點值為a的寵物，而它本身希望領(lǐng)養(yǎng)的寵物的特點值為b，那么這個領(lǐng)養(yǎng)者的不滿意程度為abs(a-b)�！救蝿�(wù)描述】你得到了一年當(dāng)中，領(lǐng)養(yǎng)者和被收養(yǎng)寵物到來收養(yǎng)所的情況，希望你計算所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和。這一年初始時，收養(yǎng)所里面既沒有寵物，也沒有領(lǐng)養(yǎng)者。

Input

    第一行為一個正整數(shù)n，n<=80000，表示一年當(dāng)中來到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的總數(shù)。接下來的n行，按到來時間的先后順序描述了一年當(dāng)中來到收養(yǎng)所的寵物和領(lǐng)養(yǎng)者的情況。每行有兩個正整數(shù)a, b，其中a=0表示寵物，a=1表示領(lǐng)養(yǎng)者，b表示寵物的特點值或是領(lǐng)養(yǎng)者希望領(lǐng)養(yǎng)寵物的特點值。（同一時間呆在收養(yǎng)所中的，要么全是寵物，要么全是領(lǐng)養(yǎng)者，這些寵物和領(lǐng)養(yǎng)者的個數(shù)不會超過10000個）

Output

    僅有一個正整數(shù)，表示一年當(dāng)中所有收養(yǎng)了寵物的領(lǐng)養(yǎng)者的不滿意程度的總和mod 1000000以后的結(jié)果。

Sample Input

5

    0 2

    0 4

    1 3

    1 2

    1 5

   

Sample Output

3

    (abs(3-2) + abs(2-4)=3，最后一個領(lǐng)養(yǎng)者沒有寵物可以領(lǐng)養(yǎng))

   

HINT

Source

    Splay

    這道題的方法還是比較好想的。

    首先我們可以發(fā)現(xiàn)，收養(yǎng)所中不可能既有寵物又有主人，

電腦資料

《bzoj1208[HNOI2004]寵物收養(yǎng)所》(http://www.ishadingyu.com)。

    所以我們就可以用一顆平衡樹維護沒有主人的寵物或者沒有寵物的主人，并且用一個標(biāo)記記錄現(xiàn)在平衡樹維護的是主人還是寵物。

    那么對于每次操作，如果平衡樹為空或者該操作與標(biāo)記相同，就把這個數(shù)插入到平衡樹中，反之則刪去前驅(qū)和后繼中更接近它的一個數(shù)。

    注意這道題輸出結(jié)果要取模，為什么每次都看不見取模呢...=_=

#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include#include<cstdlib>#define F(i,j,n) for(int i=j;i<=n;i++)#define D(i,j,n) for(int i=j;i>=n;i--)#define LL long long#define pa pair<int,int>#define MAXN 80005#define INF 1000000000000#define mod 1000000using namespace std;int rt=0,tot=0,l[MAXN],r[MAXN];LL n,x,y,flag=0,sum=0,sz=0,v[MAXN],rnd[MAXN];inline LL read(){	LL x=0,f=1;char ch=getchar();	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}	return x*f;}inline void rturn(int &k){int tmp=l[k];l[k]=r[tmp];r[tmp]=k;k=tmp;}inline void lturn(int &k){int tmp=r[k];r[k]=l[tmp];l[tmp]=k;k=tmp;}inline void ins(int &k,LL x){	if (!k){k=++tot;l[k]=r[k]=0;v[k]=x;rnd[k]=rand();return;}	if (x<v[k]){ins(l[k],x);if else="" if="" inline="" int="" k="l[k]+r[k];" ll="" void="">x) del(l[k],x);	else del(r[k],x);}inline LL pre(int k,LL x){	if (!k) return -INF;	if (x==v[k]) return v[k];	if (x<v[k]) else="" if="" inline="" int="" ll="" return="" tmp="pre(r[k],x);" x="=v[k])">v[k]) return suc(r[k],x);	else	{		LL tmp=suc(l[k],x);		return tmp==INF?v[k]:tmp;	}}inline void solve(LL x){	LL ans=pre(rt,x),tmp=suc(rt,x);	if (abs(x-tmp)</p></v[k])></v[k]){ins(l[k],x);if></int,int></cstdlib></cstring></cmath></cstdio></iostream>