题目思路：splay，主要用到找某个数(不一定在树中)的前驱，后继，和插入，删除。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define mod 1000000
using namespace std;
#define inf 0x3f3f3f3f
#define Max 84000
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int p[Max],ch[Max][2],top1,ans,val[Max],root;
int num[2];
void debug();
void newnode(int &x,int fa,int data)
{
x=++top1;
p[x]=fa;
val[x]=data;
ch[x][0]=ch[x][1]=0;
}
void init()
{
top1=0;ans=0;
newnode(root,0,-inf);
newnode(ch[root][1],root,inf);
num[0]=num[1]=0;
}
void rot(int x,int f)
{
int y=p[x];
ch[y][!f]=ch[x][f];
p[ch[x][f]]=y;
if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x;
p[x]=p[y];
ch[x][f]=y;
p[y]=x;
if(p[x]==0)
root=x;
}
void splay(int x,int goal)
{
while(p[x]!=goal)
{
if(p[p[x]]==goal)
{
rot(x,ch[p[x]][0]==x);
}
else
{
int y=p[x];
int f=(ch[p[y]][0]==y);
if(ch[y][f]==x)
{
rot(x,!f),rot(x,f);
}
else
{
rot(y,f),rot(x,f);
}
}
}
if(!goal) root=x;
}
int pre(int a)
{
int x=root;
int tmp;
while(x)
{
if(val[x]==a)
return x;
if(val[x]<a) tmp=x;
x=ch[x][val[x]<a];
}
return tmp;
}
int suc(int a)
{
int x=root;
int tmp;
while(x)
{
if(val[x]==a)
return x;
if(val[x]>a) tmp=x;
x=ch[x][val[x]<a];
}
return tmp;
}
void ins(int a)
{
int x=root;
while(ch[x][val[x]<a]) x=ch[x][val[x]<a];
newnode(ch[x][val[x]<a],x,a);
splay(ch[x][val[x]<a],0);
}
void del(int x)
{
splay(x,0);
int tmp=ch[root][1];
while(ch[tmp][0]) tmp=ch[tmp][0];
splay(tmp,root);
ch[tmp][0]=ch[root][0];
p[ch[root][0]]=tmp;
p[tmp]=0;
root=tmp;
}
int main()
{
int n,ty,a;
while(scanf("%d",&n)!=EOF)
{
init();
while(n--)
{
scanf("%d%d",&ty,&a);
if(num[!ty])
{
int tmp1=pre(a),tmp2=suc(a);
if(a-val[tmp1]<=val[tmp2]-a)
{
ans+=a-val[tmp1];
ans%=mod;
del(tmp1);
num[!ty]--;
}
else
{
ans+=val[tmp2]-a;
del(tmp2);
ans%=mod;
num[!ty]--;
}
}
else
{
num[ty]++;
ins(a);
}
}
printf("%dn",ans);
}
}
