#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Nm=1e5+10;
int tot=0,root=0,root1=0;;
int size[Nm],dat[Nm],ch[Nm][3];
ll val[Nm];
inline void build(int x){
	tot++;
	size[tot]=1;
	val[tot]=x;
	dat[tot]=rand();
	ch[tot][0]=ch[tot][1]=0;
}
inline void pushup(int id){
	size[id]=size[ch[id][0]]+size[ch[id][1]]+1;
}
inline void split(int u,int x,int &L,int &R){
	if(u==0){
		L=R=0;
		return;
	}
	if(val[u]<=x){
		L=u;
		split(ch[u][1],x,ch[u][1],R);
	}
	else{
		R=u;
		split(ch[u][0],x,L,ch[u][0]);
	}
	pushup(u);
}
inline int merge(int L,int R){
	if(L==0||R==0)return L+R;
	if(dat[L]>dat[R]){
		ch[L][1]=merge(ch[L][1],R);
		pushup(L);
		return L;
	}
	else{
		ch[R][0]=merge(L,ch[R][0]);
		pushup(R);
		return R;
	}
}
inline void insert(int x){
	build(x);
	int L,R;
	split(root,x,L,R);
	root=merge(merge(L,tot),R);
}
inline void insert1(int x){
	build(x);
	int L,R;
	split(root1,x,L,R);
	root1=merge(merge(L,tot),R);
}
inline void del(int x){
	int L,R,p;
	split(root,x,L,R);
	split(L,x-1,L,p);
	p=merge(ch[p][0],ch[p][1]);
	root=merge(merge(L,p),R);
}
inline void del1(int x){
	int L,R,p;
	split(root1,x,L,R);
	split(L,x-1,L,p);
	p=merge(ch[p][0],ch[p][1]);
	root1=merge(merge(L,p),R);
}
inline int fin(int u,int x){
	if(size[ch[u][0]]+1==x)return u;
	if(x<=size[ch[u][0]])return fin(ch[u][0],x);
	else return fin(ch[u][1],x-ch[u][0]-1);
}
inline int before(int x){
	int L,R;
	split(root,x,L,R);
	if(!L)return -1e9;
	int aa=fin(L,size[L]);
	root=merge(L,R);
	return val[aa];
}
inline int before1(int x){
	int L,R;
	split(root1,x,L,R);
	if(!L)return -1e9;
	int aa=fin(L,size[L]);
	root1=merge(L,R);
	return val[aa];
}
inline int after(int x){
	int L,R;
	split(root,x-1,L,R);
	if(!R)return 1e9;
	int aa=fin(R,1);
	root=merge(L,R);
	return val[aa];
}
inline int after1(int x){
	int L,R;
	split(root1,x-1,L,R);
	if(!R)return 1e9;
	int aa=fin(R,1);
	root1=merge(L,R);
	return val[aa];
}
int main(){
	int n;
	cin>>n;
	int op,x;
	ll ans=0,bas=1e6;
	ll i1,i2;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&op,&x);
		if(op==0){
			if(size[root1]==0) insert(x);
			else{
				i1=before1(x);
				i2=after1(x);
				if(x-i1<i2-x) {del1(i1);ans=(ans+x-i1)%bas;}
				else if(x-i1>i2-x) {del1(i2);ans=(ans+i2-x)%bas;}
				else {del1(i1);ans=(ans+x-i1)%bas;}
			}
		}
		if(op==1){
			if(size[root]==0) insert1(x);
			else{
				i1=before(x);
				i2=after(x);
				if(x-i1<i2-x) {del(i1);ans=(ans+x-i1)%bas;}
				else if(x-i1>i2-x) {del(i2);ans=(ans+i2-x)%bas;}
				else {del(i1);ans=(ans+x-i1)%bas;}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

如题