题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1208
题意：
有一个宠物收养所，在接下来一段时间内会陆续有一些宠物进到店里，或是一些人来领养宠物。宠物和人的总数量为n。
t = 0代表宠物，t = 1代表人。
宠物和人分别有一个特点值a和b。有两种情况：
（1）店里全是宠物，这时进来一个人来领养宠物。那么他会领养走abs(a-b)最小的那只宠物（b = a - x or a + x）。
如果使得abs(a-b)最小的有不止一只宠物，那么b = a - x的那只会被领养走。
（2）店里全是等待的人。这事有一只宠物被送进店里，那么它会被abs(a-b)最小的那个人领养走（a = b - x or b + x）。
如果使得abs(a-b)最小的不只有一个人，那么宠物会被a = b - x的人领养走。
按照依次来到店里的顺序，给出a,b。
a = 0代表宠物，a = 1代表人。b为对应的特点值。
定义每一次领养的不满意度 = abs（宠物特点值 - 人的特点值）
问你所有不满意度之和 MOD 1000000。
题解：
Splay。
分析：
（1）在每一个时刻（除了正在领养），店里要么全是宠物，要么全是人，要么为空。
（2）在本题中，除了只能是人和宠物匹配这个特性，人和宠物是等价的，都可以在店里等待。
（3）有可能先进来一大堆宠物，再进来一大堆人。这时搜索树会退化成链，所以要用splay。
实现：
每输入一对a,b:
（1）如果店为空，那么将东西加入树中，并将树的类型改为a。
（2）如果进来一个同类，那么将当前东西加入树中。
（3）如果进来一个异类，那么找出对于这个异类的特点值的前驱pre与后继suc（类型均为pair<int,int>(dif,idx)）。
将被删除的东西为res = min(pre,suc)。
所以erase(res.second)，并更新答案ans = (ans + res.first) % MOD。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 80005
#define MOD 1000000
#define INF 100000000 using namespace std; int n,a,b;
int ans=;
int type;
int siz=;
int tot=;
int root=-;
int dat[MAX_N];
int par[MAX_N];
int lson[MAX_N];
int rson[MAX_N]; void rotate(int x,int type,int *lson,int *rson)
{
if(type==) swap(lson,rson);
int y=par[x];
int z=par[y];
lson[y]=rson[x];
if(rson[x]!=-) par[rson[x]]=y;
par[x]=z;
if(z!=-)
{
if(lson[z]==y) lson[z]=x;
else rson[z]=x;
}
rson[x]=y;
par[y]=x;
} void splay(int x,int act)
{
while(par[x]!=act)
{
int y=par[x];
int z=par[y];
if(z==act)
{
if(lson[y]==x) rotate(x,,lson,rson);
else rotate(x,,lson,rson);
}
else
{
if(lson[z]==y && lson[y]==x)
{
rotate(y,,lson,rson);
rotate(x,,lson,rson);
}
if(rson[z]==y && rson[y]==x)
{
rotate(y,,lson,rson);
rotate(x,,lson,rson);
}
if(rson[z]==y && lson[y]==x)
{
rotate(x,,lson,rson);
rotate(x,,lson,rson);
}
if(lson[z]==y && rson[y]==x)
{
rotate(x,,lson,rson);
rotate(x,,lson,rson);
}
}
}
if(act==-) root=x;
} int find(int val)
{
int now=root;
while(now!=-)
{
if(val==dat[now]) return now;
if(val<dat[now]) now=lson[now];
if(val>dat[now]) now=rson[now];
}
return -;
} void new_node(int val,int p,int &kid)
{
dat[tot]=val;
par[tot]=p;
lson[tot]=-;
rson[tot]=-;
kid=tot;
splay(tot,-);
tot++;
} void insert(int val)
{
siz++;
if(root==-)
{
int temp;
root=tot;
new_node(val,-,temp);
return;
}
int now=root;
while()
{
if(val==dat[now]) return;
if(val<dat[now])
{
if(lson[now]==-)
{
new_node(val,now,lson[now]);
return;
}
else now=lson[now];
}
if(val>dat[now])
{
if(rson[now]==-)
{
new_node(val,now,rson[now]);
return;
}
else now=rson[now];
}
}
} void erase(int x)
{
siz--;
splay(x,-);
if(lson[x]==- && rson[x]==-)
{
root=-;
return;
}
if(lson[x]==-)
{
root=rson[x];
par[rson[x]]=-;
return;
}
if(rson[x]==-)
{
root=lson[x];
par[lson[x]]=-;
return;
}
int pre=lson[root];
while(rson[pre]!=-) pre=rson[pre];
splay(pre,x);
par[pre]=-;
rson[pre]=rson[x];
par[rson[x]]=pre;
root=pre;
} pair<int,int> precursor(int val)
{
int now=root;
int pre=-;
int dif=INF;
while(now!=-)
{
if(dat[now]<val && val-dat[now]<dif)
{
pre=now;
dif=val-dat[now];
}
if(dat[now]>val) now=lson[now];
else now=rson[now];
}
return pair<int,int>(dif,pre);
} pair<int,int> succeed(int val)
{
int now=root;
int suc=-;
int dif=INF;
while(now!=-)
{
if(dat[now]>val && dat[now]-val<dif)
{
suc=now;
dif=dat[now]-val;
}
if(dat[now]>val) now=lson[now];
else now=rson[now];
}
return pair<int,int>(dif,suc);
} int main()
{
cin>>n;
for(int i=;i<n;i++)
{
cin>>a>>b;
if(siz==)
{
insert(b);
type=a;
}
else
{
if(a==type) insert(b);
else
{
pair<int,int> pre=precursor(b);
pair<int,int> suc=succeed(b);
pair<int,int> res=min(pre,suc);
erase(res.second);
ans=(ans+res.first)%MOD;
}
}
}
cout<<ans<<endl;
}