Splay

发布于:2023-01-22 ⋅ 阅读:(241) ⋅ 点赞:(0)

S p l a y Splay Splay 的性质

S p l a y Splay Splay ,比 T r e a p Treap Treap 更加灵活,更有拓展性的平衡树。

S p l a y Splay Splay 是以每一次插入,询问都将节点旋转到根的 B S T BST BST

g e t - s i z e get\text{-} size get-size 操作

计算以 x x x 为根的子树的大小。

inline void get_size(int x) 
{
	splay[x].size = splay[lson(x)].size + splay[rson(x)].size + splay[x].cnt;
}

r o t a t e rotate rotate 旋转操作

x x x 旋转到 父节点 y y y 的位置。

inline void rotate(int x) 
{
	int y=splay[x].p;
	int z=splay[y].p;
	int yson=(lson(y)==x?0:1);//x是y的那个儿子
	int zson=(lson(z)==y?0:1);//z同理
	//将x与z之间建立关系
	splay[z].son[zson]=x;
	splay[x].p=z;
	//将y与x的yson^1节点建立关系
	splay[y].son[yson]=splay[x].son[yson^1];
	splay[splay[x].son[yson^1]].p=y;
	//将y与x节点建立关系
	splay[x].son[yson^1]=y;
	splay[y].p=x;
	//重新计算子树x与y的大小
	get_size(y);
	get_size(x);
}

S p l a y Splay Splay 核心操作

x x x 旋转到 T O TO TO 的儿子处。

rotate((lson(z)==y and lson(y)==x)?y:x); \text{rotate((lson(z)==y and lson(y)==x)?y:x);} rotate((lson(z)==y and lson(y)==x)?y:x); 的原因是 如果只旋转 x x x 就会使树的高度不变,如下图:

所以我们可以在 x , y , z x,y,z x,y,z 在同一侧时先旋转 y y y 后旋转 x x x

注意特判 z z z 为目标节点的情况。

inline void splay_to(int x,int TO) 
{
	while(splay[x].p!=TO)
	{
		int y=splay[x].p;
		int z=splay[y].p;
		if(z!=TO)
			rotate((lson(z)==y&&lson(y)==x)?y:x);
		rotate(x);
	}
	if(TO==0)root=x;
}

i n s e r t insert insert 插入操作

首先找到 x x x 得插入位置。

若存在值为 x x x 的节点则 s p l a y [ n o w ] c n t + + splay \text{[} now \text{]} _cnt ++ splay[now]cnt++

否则新建节点并记录新节点的各项的值与父亲节点的儿子节点指向。

最后将节点旋转到根。

inline void splay_insert(int x)
{
	int now=root,father=0;
	while(now!=0&&splay[now].k!=x)
	{
		father=now;
		now=splay[now].son[splay[now].k<x];
	}
	if(now)
	{
		splay[now].cnt++;
	}
	else
	{
		now=++tot;
		if(father)
			splay[father].son[splay[father].k<x]=now;
		splay[now].p=father;
		splay[now].k=x;
		splay[now].son[0]=splay[now].son[1]=0;
		splay[now].size=splay[now].cnt=1;
	}
	splay_to(now,0);
}

s p l a y - f i n d - m o v e splay \text{-} find \text{-} move splay-find-move

意义:将值为 x x x 的节点移动到根。

将值为 x x x 的节点移动到根后左子树都是小于 x x x 的节点(包含 − i n f -inf inf),那么值为 x x x 的节点的排名就是根的左子树的大小。

值为 x x x 的节点可能不存在所以要特判根节点的值时否小于 x x x

r a n k ( x ) = s p l a y [ s p l a y [ r o o t ] . s o n [ 0 ] ] . s i z e + ( s p l a y [ r o o t ] . k < x ? s p l a y [ r o o t ] . c n t : 0 ) ; rank(x)=splay[splay[root].son[0]].size+(splay[root].k<x?splay[root].cnt:0); rank(x)=splay[splay[root].son[0]].size+(splay[root].k<x?splay[root].cnt:0);

inline void splay_find_move_find_rank(int x)
{
	int now=root;
	if(root==0)return;
	while(splay[now].son[splay[now].k<x]!=0&&splay[now].k!=x)
	{
		now=splay[now].son[splay[now].k<x];
	}
	splay_to(now,0);
}

前驱和后继

将值为 x x x 的节点移动到根,那么根的左子树的最大值就是 x x x 的前驱,后继同理。

因为值为 x x x 的节点可能不存在所以要特判:

if(splay[now].k<x&&op==0||splay[now].k>x&&op==1)
	return now;

返回的是前驱或后继的节点编号。

inline int find_pre_nxt(int x,int op)//op==0是前驱,op==1是后继
{
	splay_find_move_find_rank(x);
	int now=root;
	if(splay[now].k<x&&op==0||splay[now].k>x&&op==1)
		return now;
	now=splay[now].son[op];
	while(splay[now].son[op^1]!=0)
	{
		now=splay[now].son[op^1];
	}
	return now;
}

S p l a y − d e l e t e Splay - delete Splaydelete

将值为 x x x 的节点的前驱移动到根,后继移动到前驱的右儿子处。

若值为 x x x 的节点的 c n t > 1 cnt>1 cnt>1 s p a l y [ x ] . c n t − − spaly \text[x] .cnt-- spaly[x].cnt ,并移动到根节点。

若为 x x x 的节点的 c n t = 1 cnt=1 cnt=1 则删除 n o w now now n x t nxt nxt 的联系即可。

最后重新计算以 n x t , p r e nxt,pre nxt,pre 为根的子树的大小即可。

值为 x x x 的节点一定是后继的左儿子。
若此时值为 x x x 的节点的左子树不为空则值为 x x x 的节点的左节点的值大于前驱并小于 x x x
那么值为 x x x 的节点的左节点为前驱与前驱在跟节点处矛盾,故为 x x x 的节点的左子树为空。
右子树同理。
所以值为 x x x 的节点的左右子树为空。

inline void splay_delete(int x)
{	
	int pre=find_pre_nxt(x,0);
	int nxt=find_pre_nxt(x,1);
	splay_to(pre,0);
	splay_to(nxt,pre);
	int now=splay[nxt].son[0];
	if(splay[now].cnt>1)
	{
		splay[now].cnt--;
		splay_to(now,0);
	}
	else
	{
		splay[nxt].son[0]=0;
	}
	get_size(nxt);
	get_size(pre);
}

s p l a y − f i n d − n u m b e r splay - find -number splayfindnumber

查找排名为 x x x 的节点的值,递归求解,最后将节点移动到根节点。

inline int find_number(int now,int k)
{
	if(k<=splay[lson(now)].size)
		return find_number(splay[now].son[0],k);
	else
	if(k>splay[lson(now)].size+splay[now].cnt)
		return find_number(rson(now),k-splay[lson(now)].size-splay[now].cnt);
	else
	{
		int dd=splay[now].k;
		splay_to(now,0);
		return dd;
	}
}

总代码(P6136

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
namespace Splays
{
	#define lson(x) splay[x].son[0]
	#define rson(x) splay[x].son[1]
	const int N=2e6+1;
	struct Spaly
	{
		int k,p,son[2],size,cnt;
	}splay[N];
	int tot,root,n,m,ans,last;
	inline int read()
	{
		int x=0,f=1;
		char ch=getchar();
		while(!isdigit(ch))
		{
			if(ch=='-')f=-f;
			ch=getchar();
		}
		while(isdigit(ch))
		{
			x=(x<<3)+(x<<1)+ch-'0';
			ch=getchar();
		}
		return x*f;
	}
	inline void write(int x)
	{
		if(x<0)putchar('-'),x=-x;
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}	
	inline void get_size(int x) 
	{
		splay[x].size = splay[lson(x)].size + splay[rson(x)].size + splay[x].cnt;
	}
	inline void rotate(int x) 
	{
		int y=splay[x].p;
		int z=splay[y].p;
		int yson=(lson(y)==x?0:1);
		int zson=(lson(z)==y?0:1);
		
		splay[z].son[zson]=x;
		splay[x].p=z;
		splay[y].son[yson]=splay[x].son[yson^1];
		splay[splay[x].son[yson^1]].p=y;
		splay[x].son[yson^1]=y;
		splay[y].p=x;
		
		get_size(y);
		get_size(x);
	}
	inline void splay_to(int x,int TO) 
	{
		while(splay[x].p!=TO)
		{
			int y=splay[x].p;
			int z=splay[y].p;
			if(z!=TO)
				rotate((lson(z)==y&&lson(y)==x)?y:x);
			rotate(x);
		}
		if(TO==0)root=x;
	}
	inline void splay_insert(int x)
	{
		int now=root,father=0;
		while(now!=0&&splay[now].k!=x)
		{
			father=now;
			now=splay[now].son[splay[now].k<x];
		}
		if(now)
		{
			splay[now].cnt++;
		}
		else
		{
			now=++tot;
			if(father)
				splay[father].son[splay[father].k<x]=now;
			splay[now].p=father;
			splay[now].k=x;
			splay[now].son[0]=splay[now].son[1]=0;
			splay[now].size=splay[now].cnt=1;
		}
		splay_to(now,0);
	}
	inline void splay_find_move_find_rank(int x)
	{
		int now=root;
		if(root==0)return;
		while(splay[now].son[splay[now].k<x]!=0&&splay[now].k!=x)
		{
			now=splay[now].son[splay[now].k<x];
		}
		splay_to(now,0);
	}
	inline int find_pre_nxt(int x,int op)
	{
		splay_find_move_find_rank(x);
		int now=root;
		if(splay[now].k<x&&op==0||splay[now].k>x&&op==1)
			return now;
		now=splay[now].son[op];
		while(splay[now].son[op^1]!=0)
		{
			now=splay[now].son[op^1];
		}
		return now;
	}
	inline void splay_delete(int x)
	{	
		int pre=find_pre_nxt(x,0);
		int nxt=find_pre_nxt(x,1);
		splay_to(pre,0);
		splay_to(nxt,pre);
		int now=splay[nxt].son[0];
		if(splay[now].cnt>1)
		{
			splay[now].cnt--;
			splay_to(now,0);
		}
		else
		{
			splay[nxt].son[0]=0;
		}
		get_size(nxt);
		get_size(pre);
	}
	inline int find_number(int now,int k)
	{
		if(k<=splay[lson(now)].size)
			return find_number(splay[now].son[0],k);
		else
		if(k>splay[lson(now)].size+splay[now].cnt)
			return find_number(rson(now),k-splay[lson(now)].size-splay[now].cnt);
		else
		{
			int dd=splay[now].k;
			splay_to(now,0);
			return dd;
		}
	}
	void main()
	{
		splay_insert(-inf);
		splay_insert(inf);
		n=read();
		m=read();
		int op,x;
		for(int i=1; i<=n; i++)
		{
			x=read();
			splay_insert(x);
		}
		for(int i=1; i<=m; i++)
		{
			op=read();
			x=read();
			x^=last;
			if(op==1)splay_insert(x);
			if(op==2)splay_delete(x);
			if(op==3)
			{
				splay_find_move_find_rank(x);
				last=splay[splay[root].son[0]].size+(splay[root].k<x?splay[root].cnt:0);
			}
			if(op==4)
			{
				last=find_number(root,1+x);
			}
			if(op==5)
			{
				last=splay[find_pre_nxt(x,0)].k;
			}
			if(op==6)
			{
				last=splay[find_pre_nxt(x,1)].k;
			}
			if(op!=1&&op!=2)
			{
				ans^=last;
			}
		}
		write(ans);
		return;
	}
}
signed main()
{
	Splays::main();
}

网站公告

今日签到

点亮在社区的每一天
去签到