大致题意：如果一个人来的时候有狗就挑狗，没有就留下来等；狗也是，有很多人来等着领养就挑人，没有就留下来。最后使喜爱值(？)之和最小。挑选的方式是取喜爱值(=|a-b|)最大的(相同则选小的那个)
【超级简化版= =如果不是已经理解了题意可能我自己都看不懂Orz】
题解：这个跟 营业额统计 那题差不多，多了个标记。标记一下当前这个树里的是人还是狗。判断一下当前操作的与树里的是不是同种生物，然后相应做出处理就好了。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 101000
#define mod 1000000
int root;
struct node
{
int d,c,f,son[2];
}tr[maxn*2];int len,bk;
void updata(int now)
{
int lc=tr[now].son[0],rc=tr[now].son[1];
tr[now].c=tr[lc].c+tr[rc].c+1;
}
void add(int d,int f)
{
len++;
tr[len].son[0]=tr[len].son[1]=0;
tr[len].c=1;tr[len].d=d;tr[len].f=f;
if (d<tr[f].d) tr[f].son[0]=len;else tr[f].son[1]=len;
}
void rotate(int x)
{
int y=tr[x].f,z=tr[y].f,w,r,R;
if (x==tr[y].son[0]) w=1;else w=0;
r=tr[x].son[w];R=y;
tr[R].son[1-w]=r;
if (r!=0) tr[r].f=R;
r=x;R=z;
tr[R].son[ (tr[R].son[0]==y)?0:1]=r;
tr[r].f=R;
r=y;R=x;
tr[R].son[w]=r;
tr[r].f=R;
updata(y);updata(x);
}
void splay(int x,int rt)
{
while (tr[x].f!=rt)
{
int y=tr[x].f,z=tr[y].f;
if (z==rt) rotate(x);
else
{
if ((y==tr[z].son[0])==(x==tr[y].son[0])) rotate(y);
else rotate(x);rotate(x);
}
}if (rt==0) root=x;
}
int findip(int d)
{
int x=root;
while (tr[x].d!=d)
{
if (d<tr[x].d)
{
if (tr[x].son[0]!=0) x=tr[x].son[0];else break;
}else
{
if (tr[x].son[1]!=0) x=tr[x].son[1];else break;
}
}return x;
}
void ins(int d)
{
if (root==0) {add(d,0);root=len;return;}
int x=findip(d);
add(d,x);
updata(x);
splay(x,0);
}
void del(int d)
{
int x=findip(d);splay(x,0);
if (tr[x].son[0]==0 && tr[x].son[1]==0) root=len=0;
else if (tr[x].son[0]==0 && tr[x].son[1]!=0) {root=tr[x].son[1];tr[root].f=0;}
else if (tr[x].son[1]==0 && tr[x].son[0]!=0) {root=tr[x].son[0];tr[root].f=0;}
else
{
int p=tr[x].son[0];
while (tr[p].son[1]!=0) p=tr[p].son[1];
splay(p,x);root=p;
tr[p].f=0;
tr[p].son[1]=tr[x].son[1];
tr[tr[x].son[1]].f=p;
updata(p);
}
}
int findqianji(int d)
{
int x=findip(d);splay(x,0);
if (d==tr[x].d) return d;
if (d<tr[x].d && tr[x].son[0]!=0)
{
x=tr[x].son[0];
while (tr[x].son[1]!=0) x=tr[x].son[1];
}if (d<tr[x].d) x=0;
return tr[x].d;
}
int findhouji(int d)
{
int x=findip(d);splay(x,0);
if (d==tr[x].d) return d;
if (d>tr[x].d && tr[x].son[1]!=0)
{
x=tr[x].son[1];
while (tr[x].son[0]!=0) x=tr[x].son[0];
}if (d>tr[x].d) x=0;
return tr[x].d;
}
int main()
{
//freopen("pet.in","r",stdin);
//freopen("pet.out","w",stdout);
int n,i,c,x,ans=0;
scanf("%d",&n);bk=0;//bk是标记
root=len=0;
for (i=1;i<=n;i++)
{
scanf("%d%d",&c,&x);
if (root==0) bk=c;
if (c==bk) ins(x);//同种！那就插进树里
else//不同种就在树中找最接近的~(前驱or后继)
{
int p=findqianji(x);
int q=findhouji(x);
if (p==0 && q!=0) {ans+=abs(x-q);del(q);}
else if (p!=0 && q==0) {ans+=abs(x-p);del(p);}
else if (p!=0 && q!=0)
{
if (abs(x-p)>abs(x-q)) {ans+=abs(x-q);del(q);}
else {ans+=abs(x-p);del(p);}
}ans%=mod;
}
}printf("%d\n",ans);
return 0;
}