和前一题差不多，只是求前驱和后继的时候不再是树中节点，而是另外的，这不影响，差不多的方法做。

然后就是给树打标记，宠物树标记和客人树的标记。

然后就差不多啦。今天写了两题$Splay$呢。

o(╯□╰)o，求前驱后继的变量弄错了调了半天。TAT

# include <stdio.h>
using namespace std;
const int Max=200010;
int ch[Max][2],fa[Max],data[Max],root,ind=1,sum=0;
inline int min(int a,int b) {return a<b?a:b;}
inline int abs(int a) {return a<0?-a:a;}
inline void rotate(int x) {
	int y=fa[x],z=fa[y],p=ch[y][1]==x;
	fa[ch[y][p]=ch[x][p^1]]=y;
	ch[x][p^1]=y;fa[y]=x,fa[x]=z;
	if(z) ch[z][ch[z][1]==y]=x;
}
inline void splay(int x) {
	for (int y;y=fa[x];rotate(x)) 
		if(fa[y]) rotate((ch[y][0]==x)==(ch[fa[y]][0]==y)?y:x);
	root=x; 
}
int pn,pp,ss,sn;
inline void pre(int x) {
	int now=root;pp=0,pn=2100000000;
	while(1) {
		if(!now) return;
		if(data[now]<x&&(x-data[now])<pn) {pp=now;pn=x-data[now];}
		if(data[now]<x) now=ch[now][1]; else now=ch[now][0];
	}
}
inline void suc(int x) {
	int now=root;ss=0,sn=2100000000;
	while(1) {
		if(!now) return;
		if(data[now]>x&&(data[now]-x)<sn) {ss=now;sn=data[now]-x;}
		if(data[now]<x) now=ch[now][1]; else now=ch[now][0];
	}
}
inline void insert(int x,int v) {
	int y;
	while(1) {
		y=ch[x][data[x]<v];
		if(!y) {
			y=++ind;
			data[y]=v;
			ch[y][0]=ch[y][1]=0;
			fa[y]=x;ch[x][data[x]<v]=y;
			break;
		}
		x=y;
	}
	splay(y);
}
inline void del(int x) {
	splay(x);
	if(ch[x][0]==0&&ch[x][1]==0) {root=0;return;}
	if(ch[x][0]==0) {root=ch[x][1];fa[ch[x][1]]=0;return;}
	if(ch[x][1]==0) {root=ch[x][0];fa[ch[x][0]]=0;return;}
	int y=ch[x][0];
	while(ch[y][1]) y=ch[y][1];
	fa[ch[x][0]]=0;splay(y);
	fa[ch[y][1]=ch[x][1]]=y;
	root=y;
}
int n,now,first;
int main() {
	scanf("%d%d%d",&n,&now,&first);   
	root=1;ch[root][0]=ch[root][1]=0;
    fa[root]=0;data[root]=first;
    for (int i=2,kind,dat;i<=n;++i) {
    	scanf("%d%d",&kind,&dat);
    	if(root==0) {
    		now=kind;
    		root=++ind;ch[root][0]=ch[root][1]=0;
    		fa[root]=0;data[root]=dat;
		} else {
			if(now==kind) insert(root,dat);
			else {
				pre(dat);suc(dat);
				if(pn||sn) {
					int x=2100000000,xn;
					if(pn&&pn<x)x=pn,xn=pp;
					if(sn&&sn<x)x=sn,xn=ss;
					sum=(sum+x)%1000000;
					del(xn);
				}
			}
		}
	}
	printf("%d\n",sum);
	return 0;
}