上面那个不加删除，下面那个加删除。。。

删除一次要splay 两次，而且并不能降低树的高度。。。

听说splay有不可改进的常数 =3 。 2*3=6 。。。常数太大了。。。

mycode：（删除的确写丑了？？）

#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 100086
int ch[maxn][2],k[maxn],s[maxn],fa[maxn],cnt[maxn],root=0,ind=0;
void update(int x)
{
	s[x]=s[ch[x][0]]+s[ch[x][1]]+cnt[x];
	//printf("s[%d]=s[%d]+s[%d]+cnt[%d]=%d   cnt[%d]=%d\n",x,ch[x][0],ch[x][1],x,s[x],x,cnt[x]);
}
void rotate(int p)
{
	int q=fa[p],y=fa[q],x=(ch[q][1]==p);
	fa[ch[q][x]=ch[p][x^1]]=q;
	fa[ch[p][x^1]=q]=p;
	fa[p]=y;
	if(y)ch[y][ch[y][1]==q]=p;
	update(q);
}
void splay(int x,int aim=0)
{
	for(int y;(y=fa[x])!=aim;rotate(x))
		if(fa[y]!=aim)rotate((ch[y][0]==x)==(ch[fa[y]][0]==y)?y:x);
	if(aim==0)root=x;
	update(x);
}
void insert(int x,int v)
{
	if(x==0){root=x=++ind;k[x]=v;fa[x]=ch[x][0]=ch[x][1]=0;s[x]=cnt[x]=1;return;}
	while(x)
	{
		s[x]++;
		if(v==k[x]){cnt[x]++;return;}
		int &y=ch[x][v>=k[x]];
		if(y==0){y=++ind;k[y]=v;fa[y]=x;ch[y][0]=ch[y][1]=0;s[y]=cnt[y]=1;x=y;break;}
		x=y;
	}
	splay(x);
}
void del(int x,int v)
{
	while(x)
	{
		s[x]--;
		if(k[x]==v){cnt[x]--;break;}
		int &y=ch[x][v>=k[x]];
		x=y;
	}
	if(cnt[x]!=0)return;
	
	splay(x);
	if(ch[x][0]==0){root=ch[x][1];fa[root]=0;return;}
	if(ch[x][1]==0){root=ch[x][0];fa[root]=0;return;}
	
	x=ch[root][0];
	while(x){int &y=ch[x][1];if(y==0)break;x=y;}
	splay(x,root);
	
	ch[x][1]=ch[root][1];fa[ch[x][1]]=x;
	s[x]=s[root]-1;
	fa[x]=0;
	root=x;
}
int rank(int x,int v)
{
	int ret=0,ans;
	while(x)
	{
		if(v>k[x]){ret+=s[ch[x][0]]+cnt[x];x=ch[x][1];}
		else 
		{
			if(v==k[x])return ret+s[ch[x][0]]+1;
			x=ch[x][0];
		}
	}
	return ans;
}
int rkth(int x,int v)
{
	while(x)
	{
		if(v>=s[ch[x][0]]+1 && v<=s[ch[x][0]]+cnt[x])return k[x];
		if(v>s[ch[x][0]]+cnt[x]){v-=s[ch[x][0]]+cnt[x];x=ch[x][1];}
		else x=ch[x][0];
	}
}
int pre(int x,int v)
{
	int ans;
	while(x)
	{
		if(k[x]<v)ans=k[x],x=ch[x][1];
		else x=ch[x][0];
	}
	return ans;
}
int suc(int x,int v)
{
	int ans;
	while(x)
	{
		if(k[x]>v)ans=k[x],x=ch[x][0];
		else x=ch[x][1];
	}
	return ans;
}
void debug(int x)
{
	if(x==0)return;
	debug(ch[x][0]);
	printf("%5d ",k[x]);
	debug(ch[x][1]);
}
void debug2(int x)
{
	if(x==0)return;
	debug2(ch[x][0]);
	printf("%5d ",cnt[x]);
	debug2(ch[x][1]);
}
void debug()
{
	printf("de: ");debug(root);printf("\n");
	printf("de: ");debug2(root);printf("\n\n");
}
int main()
{
	//freopen("32245.in","r",stdin);
	//freopen("3224.out","w",stdout);
	int n,opt,x;
	scanf("%d",&n);
	while(n--)
	{//debug();
		scanf("%d%d",&opt,&x);
		if(opt==1){insert(root,x);}
		if(opt==2){del(root,x);}
		if(opt==3){printf("%d\n",rank(root,x));}
		if(opt==4){printf("%d\n",rkth(root,x));}
		if(opt==5){printf("%d\n",pre(root,x));}
		if(opt==6){printf("%d\n",suc(root,x));}
	}
	return 0;
}

• 全局相关文章