Splay学习——我用splay打排序

109 阅读 0 评论 72 点赞

我是靠谱客的博主刻苦柠檬，最近开发中收集的这篇文章主要介绍Splay学习——我用splay打排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Splay 学习——我用Splay打排序

Description

给出N个数，你的任务就是把这n个数从小到大排序^_

Input

第一行一个整数,N(1<=n<=200000)，表示有N个数
接下来有N行，每行一个数

Output

输出N行，表示已经排序的N个数

Sample Input

5
2
3
1
4
5

Sample Output

1
2
3
4
5

这一题相信大家都会用排序算法，之所以我用Splay，是因为OJ上找不到splay的版题。。。

也因此，我只能尝试插入、Splay操作

代码

//请自行忽略这两行注释
//#pragma GCC optimize(2)
//#pragma G++ optimize(2)
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[200010];
struct node{
	int son[2],v,t,f,size;
	node(){t=f=son[0]=son[1]=0;size=1;}
};
node no[200010];int cntn=1,root=1;
int getson(int x){return (int)(no[no[x].f].son[1]==x);}
void updata(int x)
{
	no[x].size=no[no[x].son[0]].size+no[no[x].son[1]].size+1;
}
void rotate(int x)
{
	if(!no[x].f) return ;
	int dirx,dirfa,fa,gf;
	fa=no[x].f,	gf=no[fa].f;
	dirx=getson(x),dirfa=getson(fa);
	no[fa].son[dirx]=no[x].son[dirx^1];
	no[no[fa].son[dirx]].f=fa;
	no[x].son[dirx^1]=fa;
	if(gf>0) no[gf].son[dirfa]=x;
	no[fa].f=x,no[x].f=gf;
	updata(fa);updata(x);
}
void splay(int x,int y)
{
	int z;
	while(no[x].f!=y) rotate(x);
	updata(x);
	if(y==0) root=x;
}
void ins(int v)
{
	int x=root;
	while(x)
	{
		if(v==no[x].v){no[x].t++;break;}
		if(v<no[x].v)
		{
			if(!no[x].son[0]) ++cntn,no[x].son[0]=cntn,no[cntn].v=v,no[cntn].f=x;
			x=no[x].son[0];
		}
		else
		{
			if(!no[x].son[1]) ++cntn,no[x].son[1]=cntn,no[cntn].v=v,no[cntn].f=x;
			x=no[x].son[1];
		}
	}
	splay(x,0);
}
void DFS(int x)
{
	if(x==0) return ;
	DFS(no[x].son[0]);
	for(int i=1;i<=no[x].t;i++) printf("%dn",no[x].v);
	DFS(no[x].son[1]);
}
int main()
{
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	int n,i,u,v,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	no[root].v=a[1],no[root].t=1;
	for(i=2;i<=n;i++)
	{
		ins(a[i]);
	}
	DFS(root);
	return 0;
}

交到OJ上以后。。。
TLE0！？

在这里插入图片描述

我：“肯定是splay常数太大了”

然后就开了O2

还不行？哦，双旋

void splay(int x,int y)
{
	int z;
	while(no[x].f!=y)
	{
		z=no[x].f;
		if(no[z].f!=y&&getson(z)==getson(x)) rotate(z);
		else rotate(x);
	}
	updata(x);
	if(y==0) root=x;
}

在这里插入图片描述

我：emmm…

然后就暂时用随机交换苟过去了
大概几天后，
小机房又出现了类似的声音

某同学:我SplayTLE了！

于是我baidu了一下， splay 超时

Splay的伸展

当我们把某一个点x一路旋转至某个位置时……我们可以考虑一次性进行两次旋转来让伸展之后的树更平衡。
我们一般进行如下的分类讨论：
若x的父节点即为伸展目标：直接旋转x即可。
若x的父节点不是伸展目标，且x、x的父亲、x的父亲的父亲三点共线
（即x是x的父亲的左儿子，x的父亲的父亲也是x的父亲的左儿子；或x是x的父亲的右儿子，x的父亲的父亲也是x的父亲的右儿子）。

这时先旋转x的父亲，再旋转x。

若三点不共线，对x进行两次旋转即可。

额。。。

void splay(int x,int y)
{
	int z;
	while(no[x].f!=y)
	{
		z=no[x].f;
		if(no[z].f!=y&&getson(z)==getson(x)) rotate(z);
		//else rotate(x);
		rotate(x);
	}
	updata(x);
	if(y==0) root=x;
}