bzoj1208[HNOI2004]寵物收養所

bzoj1208[HNOI2004]寵物收養所

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

Sample Output

HINT

Source

Splay

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

首先我們可以發現，收養所中不可能既有寵物又有主人。

所以我們就可以用一顆平衡樹維護沒有主人的寵物或者沒有寵物的主人，並且用一個標記記錄現在平衡樹維護的是主人還是寵物。

那麼對於每次操作，如果平衡樹為空或者該操作與標記相同，就把這個數插入到平衡樹中，反之則刪去前驅和後繼中更接近它的一個數。

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

#include
#include
#include
#include
#include
#include
#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
#define MAXN 80005
#define INF 1000000000000
#define mod 1000000
using 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 (xx) 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 (xv[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)