首先读完这题第一印象，是个裸题，很高兴。其次在打完代码之后，第二印象，很恶心，Treap的代码太长了，我今天下午敲了三遍，手都麻了。
废话不多说，正题。其实这个题不难，有几个点是很好的，首先，他的a值没有重复的，这就保证了你找前驱和后继的正确性，再次，没有宠物和人会同时在收养所内，那么你找的前驱和后继就不用判断是人还是动物。再次，就是AC了。
这个题一开始全WA，是因为没有注意前驱和后继不能为0的情况，导致自己领养自己或者自己被自己领养的情况出现，改了之后AC。
Treap的裸题，建议码一下。
直接上代码。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib> using namespace std;
const int maxn = + ; int N,flag,temp;
int Ans,size,root;
int Out = ;
int ani_cnt = ,er_cnt = ;
int pre,bac; struct data{
int l,r,w,v,size,rnd;
}tr[maxn];
void update(int k){
tr[k].size = tr[tr[k].l].size + tr[tr[k].r].size + tr[k].w;
}
void rturn(int &k){
int t = tr[k].l;tr[k].l = tr[t].r;tr[t].r = k;
tr[t].size = tr[k].size;update(k);k = t;
}
void lturn(int &k){
int t = tr[k].r;tr[k].r = tr[t].l;tr[t].l = k;
tr[t].size = tr[k].size;update(k);k = t;
}
void insert(int &k,int x){
if(k == ){
size ++;k = size;
tr[k].w = tr[k].size = ;
tr[k].v = x;tr[k].rnd = rand();
return;
}
tr[k].size ++;
if(tr[k].v == x){
tr[k].w ++;
}
else if(x < tr[k].v){
insert(tr[k].l,x);
if(tr[tr[k].l].rnd < tr[k].rnd)
rturn(k);
}
else {
insert(tr[k].r,x);
if(tr[tr[k].r].rnd < tr[k].rnd)
lturn(k);
}
}
void del(int &k,int x){
if(k == )
return;
if(tr[k].v == x){
if(tr[k].w > ){
tr[k].w --;tr[k].size --;
return;
}
if(tr[k].r*tr[k].l == )
k = tr[k].r + tr[k].l;
else if(tr[tr[k].l].rnd < tr[tr[k].r].rnd)
rturn(k),del(k,x);
else
lturn(k),del(k,x);
}
else if(x > tr[k].v)
tr[k].size --,del(tr[k].r,x);
else
tr[k].size --,del(tr[k].l,x);
}
int query_rank(int k,int x){
if(k == )
return ;
if(x == tr[k].v)
return tr[tr[k].l].size + ;
else if(x > tr[k].v)
return tr[tr[k].l].size + tr[k].w + query_rank(tr[k].r,x);
else return query_rank(tr[k].l,x);
}
int query_num(int k,int x){
if(k == )
return ;
if(x <= tr[tr[k].l].size)
return query_num(tr[k].l,x);
else if(x > tr[tr[k].l].size + tr[k].w)
return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
else return tr[k].v;
}
void query_pre(int k,int x){
if(k == )
return;
if(x > tr[k].v){
Ans = k;query_pre(tr[k].r,x);
}
else query_pre(tr[k].l,x);
}
void query_sub(int k,int x){
if(k == )
return;
if(x < tr[k].v){
Ans = k;query_sub(tr[k].l,x);
}
else query_sub(tr[k].r,x);
} int main(){
freopen("pet.in","r",stdin);
freopen("pet.out","w",stdout);
scanf("%d",&N);
for(int i = ;i <= N;++ i){
scanf("%d%d",&flag,&temp);
if(!flag){
insert(root,temp);
ani_cnt ++;
if(er_cnt >= ani_cnt){//如果人多动物少，那么这个动物立刻被领养
query_pre(root,temp);pre = tr[Ans].v;Ans = ;
query_sub(root,temp);bac = tr[Ans].v;Ans = ;
if(pre == bac){
Out += abs(pre-temp);
del(root,pre);del(root,temp);
}
else{
if(temp-pre < bac-temp){
if(pre){
Out += temp-pre;
del(root,pre);del(root,temp);
}
else{
Out += bac-temp;
del(root,bac);del(root,temp);
} }
else{
if(bac){
Out += bac-temp;
del(root,bac);del(root,temp);
}
else{
Out += temp-pre;
del(root,pre);del(root,temp);
}
}
}
--er_cnt;--ani_cnt;
}
}
else{
insert(root,temp);
er_cnt ++;
if(ani_cnt >= er_cnt){//如果动物多人少，那么这个人立刻领养一个动物
query_pre(root,temp);pre = tr[Ans].v;Ans = ;
query_sub(root,temp);bac = tr[Ans].v;Ans = ;
if(pre == bac){
Out += abs(pre-temp);
del(root,pre);del(root,temp);
}
else{
if(temp-pre < bac-temp){
if(pre){
Out += temp-pre;
del(root,pre);del(root,temp);
}
else{
Out += bac-temp;
del(root,bac);del(root,temp);
}
}
else{
if(bac){
Out += bac-temp;
del(root,bac);del(root,temp);
}
else{
Out += temp-pre;
del(root,pre);del(root,temp);
}
}
}
--er_cnt;--ani_cnt;
}
}
Out %= ;
}
printf("%d",Out%);
fclose(stdin);fclose(stdout);
return ;
}