BZOJ 1208 / Luogu P2286

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=2e5+10;
const int Mod=1e6;
const int INF=0x3f3f3f3f;
int n,tot,rt,cnt,ans;

struct Node{
	int ch[2],val,ff;
}t[M];

inline void Rotate(int x){
	int y=t[x].ff,z=t[y].ff,k=(x==t[y].ch[1]);
	t[z].ch[y==t[z].ch[1]]=x;
	t[x].ff=z;
	t[y].ch[k]=t[x].ch[k^1];
	t[t[x].ch[k^1]].ff=y;
	t[x].ch[k^1]=y;
	t[y].ff=x;
}

void Splay(int x,int aim){
//	if(!x) return;
	while(t[x].ff!=aim){
		int y=t[x].ff,z=t[y].ff;
		if(z!=aim){
			if((t[z].ch[0]==y)^(t[y].ch[0]==x))
				Rotate(x);
			else Rotate(y);
		}
		Rotate(x);
	}
	if(!aim) rt=x;
}

void Insert(int x){
	int u=rt,ff=0;
	while(u&&t[u].val!=x){
		ff=u;
		u=t[u].ch[t[u].val<x];
	}
	if(!u){
		u=++tot;
		if(ff)
			t[ff].ch[t[ff].val<x]=u;
			t[u].ff=ff;
			t[u].ch[0]=t[u].ch[1]=0;
			t[u].val=x;
	}
	Splay(u,0);
}

void Find(int x){
	int u=rt;
	if(!u) return ;
	while(t[u].ch[x>t[u].val]&&x!=t[u].val)
		u=t[u].ch[x>t[u].val];
	Splay(u,0);
}

int Next(int x,int f){
	Find(x);
	int u=rt;
	if(t[u].val>=x&&f) return u;
	if(t[u].val<=x&&!f) return u;
	u=t[u].ch[f];
	while(t[u].ch[f^1])
		u=t[u].ch[f^1];
	return u;
}

int Next_Une(int x,int f){
	Find(x);
	int u=rt;
	if(t[u].val>x&&f) return u;
	if(t[u].val<x&&!f) return u;
	u=t[u].ch[f];
	while(t[u].ch[f^1])
		u=t[u].ch[f^1];
	return u;
}

void Delete(int x){
	int lt=Next_Une(x,0);
	int nt=Next_Une(x,1);
	Splay(lt,0);
	Splay(nt,lt);
	t[nt].ch[0]=0;
}

int main(){
	scanf("%d",&n);
	Insert(INF);
	Insert(-INF);
	while(n--){
		int k,x;
		scanf("%d%d",&k,&x);
		if(!cnt) Insert(x);
		if(cnt>0){
			if(!k) Insert(x);
			else{
				int a1=t[Next(x,0)].val;
				int a2=t[Next(x,1)].val;
				if(abs(a1-x)<=abs(a2-x)){
					ans+=abs(a1-x);
					Delete(a1);
				}
				else{
					(ans+=abs(a2-x))%=Mod;
					Delete(a2);
				}
			}
		}
		if(cnt<0){
			if(k) Insert(x);
			else{
				int a1=t[Next_Une(x,0)].val;
				int a2=t[Next_Une(x,1)].val;
				if(abs(a1-x)<=abs(a2-x)){
					(ans+=abs(a1-x))%=Mod;
					Delete(a1);
				}
				else{
					(ans+=abs(a2-x))%=Mod;
					Delete(a2);
				}
			}
		}
		cnt=cnt+(k==0?1:-1);
	}
	printf("%d\n",ans);
	return 0;
}