bzoj3224 普通平衡樹（splay，treap模闆）

3224: Tyvj 1728 普通平衡樹

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 19372  Solved: 8479

[Submit][Status][Discuss]

Description

您需要寫一種資料結構（可參考題目标題），來維護一些數，其中需要提供以下操作：

1. 插入x數

2. 删除x數(若有多個相同的數，因隻删除一個)

3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)

4. 查詢排名為x的數

5. 求x的前驅(前驅定義為小于x，且最大的數)

6. 求x的後繼(後繼定義為大于x，且最小的數)

Input

第一行為n，表示操作的個數,下面n行每行有兩個數opt和x，opt表示操作的序号(1<=opt<=6)

Output

對于操作3,4,5,6每行輸出一個數，表示對應答案

Sample Input

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

Sample Output

106465

84185

492737

HINT

1.n的資料範圍：n<=100000

2.每個數的資料範圍：[-2e9,2e9]

題解：平衡樹基本操作不解釋

代碼（splay版）：

#include<bits/stdc++.h>
using namespace std;
int size[1000000],cnt[1000000],lc[1000000],rc[1000000],fa[1000000],val[1000000],root,tot;
void clear(){
	root=tot=0;
	memset(size,0,sizeof(size));
	memset(cnt,0,sizeof(cnt));
}
void updata(int x){
	if(x){
		size[x]=cnt[x]+(lc[x]?size[lc[x]]:0)+(rc[x]?size[rc[x]]:0);
	}
}
void zig(int x){
	int y,z;
	if(!fa[x])return;
	y=fa[x];z=fa[y];
	if(z)
		if(lc[z]==y)lc[z]=x;
		 else rc[z]=x;
		fa[x]=z;fa[y]=x;fa[rc[x]]=y;lc[y]=rc[x];rc[x]=y;
		updata(y);updata(x);
}
void zag(int x){
	int y,z;
	if(!fa[x])return;
	y=fa[x];z=fa[y];
	if(z)
	 if(lc[z]==y)lc[z]=x;
	  else rc[z]=x;
	 fa[x]=z;fa[y]=x;fa[lc[x]]=y;rc[y]=lc[x];lc[x]=y;
	 updata(y);updata(x); 
}
void splay(int &root,int x){
	int y,z;
	while(fa[x]){
		y=fa[x];z=fa[y];
		if(z){
			if(lc[z]==y&&lc[y]==x)zig(y),zig(x);
			 else if(lc[z]==y&&rc[y]==x)zag(x),zig(x);
			  else if(rc[z]==y&&lc[y]==x)zig(x),zag(x);
			   else zag(y),zag(x);
		}
		 else if(lc[y]==x)zig(x);
		  else zag(x);
	}
	root=x;
}
void sp(int x){
	splay(root,x);
}
void insert(int &k,int key,int p){
	if(!k){
		size[k=++tot]=cnt[k]=1;
		lc[k]=rc[k]=0;
		val[k]=key;
		fa[k]=p;
		sp(k);
		return;
	}
	size[k]++;
	if(key==val[k]){
		cnt[k]++;
		return;
	}
	if(key<val[k])insert(lc[k],key,k);
	 else insert(rc[k],key,k);
}
void ins(int key){
	if(!root){
		size[root=++tot]=cnt[root]=1;
		lc[root]=rc[root]=0;
		val[root]=key;fa[root]=0;
		return;
	}
	insert(root,key,0);
}
int find(int k,int key){
	while(k){
		if(val[k]==key)break;
		k=key<val[k]?lc[k]:rc[k];
	}
	if(k)sp(k);
	return k;
}
int fin(int key){
	return find(root,key);
}
int getmin(int k){
	return lc[k]?getmin(lc[k]):k;
}
int getmax(int k){
	return rc[k]?getmax(rc[k]):k;
}
void del(int key){
	int ls,rs,x,lson;
	x=fin(key);ls=lc[x];rs=rc[x];
	if(!x)return;
	if(--cnt[x])return;
	if(!ls&&!rs){
		clear();
		return;
	}
	if(!ls)root=rs,fa[rs]=0;
	 else if(!rs)root=ls,fa[ls]=0;
	  else{
	  	lson=getmax(ls);
	  	swap(lson,ls);
	  	fa[lson]=0;sp(ls);
	  	rc[ls]=rs;fa[rs]=ls;updata(ls);
	  }
}
int findkth(int k){
	int t;
	t=root;
	while(t){
		if(size[lc[t]]<k&&k<=size[lc[t]]+cnt[t])break;
		if(k<=size[lc[t]])t=lc[t];
		 else k-=size[lc[t]]+cnt[t],t=rc[t];
	}
	sp(t);
	return t;
}
int findpre(int k,int key){
	int tmp;
	if(!k)return 0;
	if(key<=val[k])return findpre(lc[k],key);
	 else{
	 	tmp=findpre(rc[k],key);
	 	return tmp?tmp:k;
	 }
}
int findnxt(int k,int key){
	if(!k)return 0;
	if(key>=val[k])return findnxt(rc[k],key);
	 else{
	 	int tmp=findnxt(lc[k],key);
	 	return tmp?tmp:k;
	 }
}
int findpr(int key){
	return findpre(root,key); 
}
int findnx(int key){
	return findnxt(root,key);
}
int main(){
	int n,i,t1,x;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&t1,&x);
		if(t1==1)ins(x);
		if(t1==2)del(x);
		if(t1==3){
			sp(fin(x));
			printf("%d\n",size[lc[root]]+1);
		}
		if(t1==4)printf("%d\n",val[findkth(x)]);
		if(t1==5)printf("%d\n",val[findpr(x)]);
		if(t1==6)printf("%d\n",val[findnx(x)]);
	}
}
           

treap模闆：

#include<bits/stdc++.h>
using namespace std;
int rt,cnt,n,ans,vis[100001],lc[100001],rc[100001],pos[100001];
void zig(int &x){
	int y=lc[x];
	lc[x]=rc[y];rc[y]=x;
	x=y;
}
void zag(int &x){
	int y=rc[x];
	rc[x]=lc[y];lc[y]=x;
	x=y;
}
void insert(int &x,int t){
	if(!x){
		vis[x=++cnt]=t;
		pos[x]=rand();
		return;
	}
	if(t<vis[x]){
		insert(lc[x],t);
		if(pos[lc[x]]<pos[x])zig(x);
	}
	 else{
	 	insert(rc[x],t);
	 	if(pos[rc[x]]<pos[x])zag(x);
	 }
}
int getpre(int t){
	int x=rt,now=-1e9;
	while(x){
		if(t>=vis[x])now=vis[x],x=rc[x];
		 else  x=lc[x];
	}
	return now;
}
int getnext(int t){
	int x=rt,now=1e9;
	while(x){
		if(t<=vis[x])now=vis[x],x=lc[x];
		 else x=rc[x];
	}
	return now;
}
int main(){
	int t,x,y;
	scanf("%d",&n);
	scanf("%d",&ans);
	insert(rt,ans);
	while(--n){
		scanf("%d",&t);
		x=getpre(t);y=getnext(t);
		ans+=min(t-x,y-t);
		insert(rt,t);
	}
	printf("%d",ans);
}