[HNOI2004]宠物收养所 SBT

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

继续跪，在找前驱和后继的时候出错了，debug出翔了，最后下载了测试数据对拍。

在找前驱和后继的时候，可能出现前驱和后继不存在，应当返回inf才对。

每于一棵树，要么为空，要么全为宠物或者全为人，加一个标记，表示树内现在的种类，对于一个新进来的，判断是否一致，一致则插入，否则找出一个相邻的删掉。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005
#define MOD 1000000
#define inf 1<<29
using namespace std;
struct SBT{
	//左子树指针，右子树指针，大小，键值
	int left,right,size,key;
	void Init(){
		left=right=key=0;
		size=1;
	}
}T[N];
int root,tot; //根的位置以及节点个数
//左旋转处理
void Left_rot(int &x){  
	int k=T[x].right;
	T[x].right=T[k].left;
	T[k].left=x;
	T[k].size=T[x].size;
	T[x].size=T[T[x].left].size+T[T[x].right].size+1;
	x=k;
}
//右旋转处理
void Right_rot(int &x){
	int k=T[x].left;
	T[x].left=T[k].right;
	T[k].right=x;
	T[k].size=T[x].size;
	T[x].size=T[T[x].left].size+T[T[x].right].size+1;
	x=k;
}
//调整处理
void Maintain(int &r,bool flag){
	if(flag){  //更新右子树
		if(T[T[T[r].right].right].size>T[T[r].left].size)
			Left_rot(r);
		else if(T[T[T[r].right].left].size>T[T[r].left].size){
			Right_rot(T[r].right);
			Left_rot(r);
		}
		else
			return;
	} 
	else{   //更新在左子树
		if(T[T[T[r].left].left].size>T[T[r].right].size)
			Right_rot(r);
		else if(T[T[T[r].left].right].size>T[T[r].right].size){
			Left_rot(T[r].left);
			Right_rot(r);
		}
		else 
			return;
	}
	//更新子树，然后再更新根，直到平衡为止
	Maintain(T[r].left,false);
	Maintain(T[r].right,true);
	Maintain(r,false);
	Maintain(r,true);
}
//插入新节点
void Insert(int &r,int k){
	if(r==0){
		r=++tot;
		T[r].Init();
		T[r].key=k;
	}
	else{
		T[r].size++;
		if(k<T[r].key)
			Insert(T[r].left,k);
		else
			Insert(T[r].right,k);
		//插入后要调整，保证平衡
		Maintain(r,k>=T[r].key);
	}
}
//删除结点，利用的是前驱替换
int Remove(int &r,int k){
	int d_key;
	if(!r)
		return 0;
	T[r].size--;
	//前者说明就是要删的节点，后两者说明不存在此节点
	if(T[r].key==k||(T[r].left==0&&k<T[r].key)||(T[r].right==0&&k>T[r].key)){
		d_key=T[r].key;
		if(T[r].left&&T[r].right)
			T[r].key=Remove(T[r].left,k+1);
		else
			r=T[r].left+T[r].right;
		return d_key;
	}
	else return Remove(k<T[r].key?T[r].left:T[r].right,k);

}
void Delete(int &r,int delay,int min_val){
	if(!r) return;
	if(T[r].key+delay<min_val) {
		r=T[r].right;
		Delete(r,delay,min_val);
	}
	else{
		Delete(T[r].left,delay,min_val);
		T[r].size=T[T[r].right].size+T[T[r].left].size+1;
	}
}
//取得最大值，即一直遍历到最右的结点
int Get_Max(int &r){
	while(T[r].right)
		r=T[r].right;
	return r;
}
//取得最小值，即一直遍历到最左的结点
int Get_Min(int &r){
	while(T[r].left)
		r=T[r].left;
	return r;
}
//获得前驱
int Get_Pre(int &r,int y,int k){
	if(r==0){
		if(y==0)
			return inf;
		return T[y].key;
	}
	if(k>=T[r].key)
		return Get_Pre(T[r].right,r,k);
	else
		return Get_Pre(T[r].left,y,k);
}
//获得后继
int Get_Next(int &r,int y,int k){
	if(r==0) {
		if(y==0)
			return inf;
		return T[y].key;
	}
	if(k<T[r].key)
		return Get_Next(T[r].left,r,k);
	else
		return Get_Next(T[r].right,y,k);
}
//取得第K小的数，注：暂不能解决有重复数的
int Get_Min_Kth(int &r,int k){
	int t=T[T[r].left].size+1;
	if(t==k) return T[r].key;
	if(t<k)  return Get_Min_Kth(T[r].right,k-r);
	else return Get_Min_Kth(T[r].left,k);
}
//取得第K大的数
int Get_Max_Kth(int &r,int k){
	int t=T[T[r].right].size+1;
	if(t==k) return T[r].key;
	if(t<k) return Get_Max_Kth(T[r].left,k-t);
	else return Get_Max_Kth(T[r].right,k);
}
//获得结点的名次
int Get_Rank(int &r,int k){
	if(k<T[r].key) 
		return Get_Rank(T[r].left,k);
	else if(k>T[r].key)
		return Get_Rank(T[r].right,k)+T[T[r].left].size+1;
	else
		return T[T[r].left].size+1;
}
//查找树中是否存在元素
int Find(int &r,int k){
	if(!r) return 0;
	if(T[r].key==k) return 1;
	if(k<T[r].key) return Find(T[r].left,k);
	else return Find(T[r].right,k);
}
//排序
void Inorder(int &r){
	if(r==0) return;
	Inorder(T[r].left);
	printf("%d\n",T[r].key);
	Inorder(T[r].right);
}
int main(){
	int n,kind,k;
	int TreeKind;
	freopen("INPUT.001","r",stdin);
	while(scanf("%d",&n)!=EOF){
		tot=root=0;
		int ans=0,sum=0;
		while(n--){
			scanf("%d%d",&kind,&k);
			if(T[root].size==0||TreeKind==kind){
				Insert(root,k);
				TreeKind=kind;
			}
			else{
				if(Find(root,k)){
					Remove(root,k);
					continue;
				}
				int a=Get_Pre(root,0,k);
				int b=Get_Next(root,0,k);
				if(abs(a-k)<=abs(b-k)){
					ans=(ans+abs(a-k))%MOD;
					Remove(root,a);
				}
				else{
					ans=(ans+abs(b-k))%MOD;
					Remove(root,b);
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}