洛咕
题意:宠物收养场提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物.每个领养者都希望领养到自己满意的宠物，每个领养者希望领养的宠物的特点值为a（a是一个正整数，a<2^31），而每个处在收养场的宠物也有一个特点值.
宠物收养场总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少.
被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为a，那么它将会领养一只目前未被领养的宠物中特点值最接近a的一只宠物。（任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的）如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为a-b和a+b，那么领养者将会领养特点值为a-b的那只宠物。
收养宠物的人过多，假若到来一只被收养的宠物，那么能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为a，存在两个领养者他们希望领养宠物的特点值分别为a-b和a+b，那么特点值为a-b的那个领养者将成功领养该宠物。
(这两段的意思就是对于一个数x,找它的前驱和后继,如果前驱和后继与x的差值恰好相等,则选择前驱,否则选择差值较小的)
一个领养者领养了一个特点值为a的宠物，而它本身希望领养的宠物的特点值为b，那么这个领养者的不满意程度为abs(a-b)。你得到了一年当中，领养者和被收养宠物到来收养所的情况，请你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者.
分析:平衡树部分是裸模板,但是有一个细节,就是宠物树和领养者树之间的转换.bj=0,1,2分别表示宠物树,领养者树,中立树.显然一开始是中立树.
如果当前是宠物树bj=0(即宠物过多时),来一个宠物就直接插入树中,来一个领养者,直接查询前驱后继拿走一个宠物,当树中最后一个宠物被领走时,bj=2表示树是中立的.
如果当前是领养者树bj=1(即领养者过多时),来一个领养者就直接插入树中,来一个宠物,直接查询前驱后继删除一个领养者,当树中最后一个领养者离开时,bj=2表示树是中立的.
bj=2时,如果当前插入一个宠物则bj=0,否则bj=1;
#include<bits/stdc++.h>
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 100005
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
const int mod=1000000;
int p,tot,bj=2;LL ans;
int size[MAXN],num[MAXN],val[MAXN],rd[MAXN];
int son[MAXN][2];
void pushup(int p){size[p]=size[son[p][0]]+size[son[p][1]]+num[p];}
void rotate(int &p,int d){
int k=son[p][d^1];
son[p][d^1]=son[k][d];
son[k][d]=p;
pushup(p);pushup(k);p=k;
return;
}
void Insert(int &p,int x){
if(!p){
p=++tot;size[p]=num[p]=1;
val[p]=x;rd[p]=rand();
return;
}
if(val[p]==x){
size[p]++;num[p]++;
return;
}
int d=(val[p]<x);Insert(son[p][d],x);
if(rd[p]<rd[son[p][d]])rotate(p,d^1);
pushup(p);return;
}
void Delete(int &p,int x){
if(!p)return;
else if(val[p]<x)Delete(son[p][1],x);
else if(val[p]>x)Delete(son[p][0],x);
else{
if(!son[p][0]&&!son[p][1]){
size[p]--;num[p]--;
if(size[p]==0)p=0;
}
else if(!son[p][0]&&son[p][1]){
rotate(p,0);
Delete(son[p][0],x);
}
else if(son[p][0]&&!son[p][1]){
rotate(p,1);
Delete(son[p][1],x);
}
else if(son[p][0]&&son[p][1]){
int d=(rd[son[p][0]]>rd[son[p][1]]);
rotate(p,d);Delete(son[p][d],x);
}
}
pushup(p);
}
int pre(int p,int x){
if(!p)return -INF;
else if(val[p]>=x)return pre(son[p][0],x);
else return max(val[p],pre(son[p][1],x));
}
int nxt(int p,int x){
if(!p)return INF;
else if(val[p]<=x)return nxt(son[p][1],x);
else return min(val[p],nxt(son[p][0],x));
}
int main(){
int n=read();
while(n--){
int opt=read(),x=read();
if(opt==0){
if(bj==0)Insert(p,x);
else if(bj==1){
LL ans1=pre(p,x),ans2=nxt(p,x);
if(ans1==-INF&&ans2==INF)continue;
else if(ans1==-INF&&ans2!=INF){
ans+=ans2-x;Delete(p,ans2);
}
else if(ans1!=-INF&&ans2==INF){
ans+=x-ans1;Delete(p,ans1);
}
else if((ans2-x)<(x-ans1))ans+=ans2-x,Delete(p,ans2);
else ans+=x-ans1,Delete(p,ans1);
}
else if(bj==2)Insert(p,x),bj=0;
if(p==0)bj=2;
}
else{
if(bj==0){
LL ans1=pre(p,x),ans2=nxt(p,x);
if(ans1==-INF&&ans2==INF)continue;
else if(ans1==-INF&&ans2!=INF){
ans+=ans2-x;Delete(p,ans2);
}
else if(ans1!=-INF&&ans2==INF){
ans+=x-ans1;Delete(p,ans1);
}
else if((ans2-x)<(x-ans1))ans+=ans2-x,Delete(p,ans2);
else ans+=x-ans1,Delete(p,ans1);
}
else if(bj==1)Insert(p,x);
else if(bj==2)Insert(p,x),bj=1;
if(p==0)bj=2;
}
ans=(ans+mod)%mod;
}
printf("%lld
",ans);
return 0;
}