BZOJ 1208: [HNOI2004]宠物收养所

题目地址：http://www.lydsy.com/JudgeOnline/problem.php?id=1208

题目大意：对每一只新来的宠物/领养者，将与这只宠物/领养者最接近的领养者/宠物的特点值与新的特点值之差累加。

算法讨论：

        平衡树模板题，我用的是Treap。

        Part I 我的做法是开2棵Treap，一棵记录宠物的情况，另一棵记录领养者的情况，其余按照题意模拟即可。

        Part II 说一下其他大神只开一棵平衡树的做法。具体做法是当树为空时转换角色即可。

        就是这么简单~

Code：

/*
 * Problem:1208
 * Author:PYC
 */

#include <cstdio>
#include <cstdlib>
#include <algorithm>

#define maxn 100000
#define oo 1000000000

using namespace std;

int n,ans;

struct treap_tree{
int root,tot;

struct treap_node{
int key,val,aux,l,r;
}tree[maxn];

void zig(int &rt){
int t=tree[rt].l;
tree[rt].l=tree[t].r;
tree[t].r=rt;
rt=t;
}

void zag(int &rt){
int t=tree[rt].r;
tree[rt].r=tree[t].l;
tree[t].l=rt;
rt=t;
}

void insert(int &rt,int y){
if (!rt){
rt=++tot;
tree[rt].key=y;
tree[rt].val=1;
tree[rt].aux=rand()*rand();
tree[rt].l=tree[rt].r=0;
return;
}
if (y==tree[rt].key){tree[rt].val++;return;}
if (y<tree[rt].key){
insert(tree[rt].l,y);
if (tree[rt].aux>tree[tree[rt].l].aux) zig(rt);
return;
}
if (y>tree[rt].key){
insert(tree[rt].r,y);
if (tree[rt].aux>tree[tree[rt].r].aux) zag(rt);
return;
}
}

void Del(int &rt,int y){
if (!rt) return;
if (y==tree[rt].key){
if (tree[rt].val>1){tree[rt].val--;return;}
if (!tree[rt].l || !tree[rt].r){
if (!tree[rt].r) rt=tree[rt].l;
else rt=tree[rt].r;
return;
}
if (tree[tree[rt].l].aux<tree[tree[rt].r].aux){
zig(rt);
Del(tree[rt].r,y);
return;
}
else{
zag(rt);
Del(tree[rt].l,y);
return;
}
}
if (y<tree[rt].key){Del(tree[rt].l,y);return;}
if (y>tree[rt].key){Del(tree[rt].r,y);return;}
}

int pred(int rt,int y){
if (!rt) return -oo;
if (y<=tree[rt].key) return pred(tree[rt].l,y);
else return max(pred(tree[rt].r,y),tree[rt].key);
}

int succ(int rt,int y){
if (!rt) return oo;
if (y>=tree[rt].key) return succ(tree[rt].r,y);
else return min(succ(tree[rt].l,y),tree[rt].key);
}

void ins(int y){
insert(root,y);
}

void del(int y){
Del(root,y);
}

int pre(int y){
return pred(root,y);
}

int suc(int y){
return succ(root,y);
}
}tree0,tree1;

int main(){
srand(0);
scanf("%d",&n);
for (int i=1;i<=n;++i){
int x,y;
scanf("%d%d",&x,&y);
if (!x){
if (tree1.root){
int p=tree1.pre(y),s=tree1.suc(y);
if (y-p<=s-y){
tree1.del(p);
ans=(ans+y-p)%1000000;
}
else{
tree1.del(s);
ans=(ans+s-y)%1000000;
}
}
else tree0.ins(y);
}
else{
if (tree0.root){
int p=tree0.pre(y),s=tree0.suc(y);
if (y-p<=s-y){
tree0.del(p);
ans=(ans+y-p)%1000000;
}
else{
tree0.del(s);
ans=(ans+s-y)%1000000;
}
}
else tree1.ins(y);
}
}
printf("%d\n",ans);
return 0;
}

By Charlie Pan

Mar 4,2014