平衡树专题Splay

void rotate(int x)//单旋一次
{
	int f=t[x].fa;//f：父亲
	int g=t[f].fa;//g：祖父
	int son=get(x);
	if(son==1)//x是左儿子，右旋
	{
		t[f].rs=t[x].ls;
		if(t[f].rs)
		{
			t[t[f].rs].fa=f;
		}
	}
	else//x是右儿子，左旋
	{
		t[f].ls=t[x].rs;
		if(t[f].ls)
		{
			t[t[f].ls].fa=f;
		}
	}
	t[f].fa=x;//x旋为f的父节点
	if(son==1)//左旋，f变为x的左儿子
	{
		t[x].ls=f;
	}
	else//右旋，f变为x的右儿子
	{
		t[x].rs=f;
	}
	t[x].fa=g;//x现在是祖父的儿子
	if(g)//更新祖父的儿子
	{
		if(t[g].rs==f)
		{
			t[g].rs=x;
		}
		else
		{
			t[g].ls=x;
		}
	}
	Update(f);
	Update(x);
}

 void Splay(int x,int goal)
{
	if(goal==0)
	{
		root=x;
	}
	while(1)
	{
		int f=t[x].fa;//一次处理x,f,g三个节点
		int g=t[f].fa;
		if(f==goal){
			break;
		}
		if(g!=goal)//有祖父，分为一字旋和之字旋两种情况
		{
			if(get(x)==get(f))//一字旋，先旋转f,g
			{
				rotate(f);
			}
			else//之字旋，直接旋转x
			{
				rotate(x);
			}
		}
		rotate(x);
	}
	Update(x);
} 

 void Insert(int L,int len)//插入一段区间
{
	int x=kth(root,L);//x为第L个数的位置，y为第L+1个数的位置
	int y=kth(root,L+1);
	Splay(x,0);//分裂
	Splay(y,x);
    //先把x旋转到根，然后把y旋转到x的儿子，且y的儿子为空
	t[y].ls=build(1,len,y);//合并：建一棵树，挂到y的左儿子上
	Update(y);
	Update(x);
}
void Del(int L,int R)//删除区间[L+1,R]
{
	int x=kth(root,L)；
	int y=kth(root,R+1);
	Splay(x,0);//y是x的右儿子，y的左儿子是待删除的区间
	Splay(y,x);
	t[y].ls=0;//剪短左子树，等于直接删除，这里为了简单，没有释放空间
	Update(y);
	Update(x);
}

 int kth(int x) { //查询排名为x的数 
	int now = root;
	while (1) {
		if (siz[son[now][0]] >= x) now = son[now][0]; //查过头了
		else if (siz[son[now][0]] + cnt[now] >= x) return val[now]; //正好查到
		else {
			x -= (siz[son[now][0]] + cnt[now]);
			now = son[now][1]; //没查够 
		} 
	}
}

 int rank(int x) { //查询x的排名 
	int now = root, ans = 0;
	while (1) {
		if (!now) return ans + 1; //树中不存在这个数 那就是目前查到比它小的数的数目+1
		if (val[now] > x) now = son[now][0]; //要查的数比now节点的数小 说明在左子树
		else if (val[now] == x) {
			ans += siz[son[now][0]]; //比它小的数的数目
			splay(now);
			return ans + 1; 
		} else { //要查的数在左子树 
			ans += siz[son[now][0]] + cnt[now]; //此时当前节点和左子树所有数都比它小 
			now = son[now][1];
		}
	} 
}

 int findpre() { //查询根节点的前驱对应的结点编号 
	int now = son[root][0]; //首先进入左子树 因为左子树的所有数都比它小 
	while (son[now][1]) now = son[now][1]; //然后一直往大的走 找最大的
	return now; 
} 

int findnxt() { //跟上面同理 
	int now = son[root][1];
	while (son[now][0]) now = son[now][0];
	return now;
}

···

else if (opt == 5) {
	splay.insert(x); //把x先旋到根节点 而且一定要插入而不是直接旋 防止树上本来就没有x
	printf("%d\n", splay.val[splay.findpre()]);
	splay.del(x); //用完删掉 
} else {
	splay.insert(x); //同上 
	printf("%d\n", splay.val[splay.findnxt()]);
	splay.del(x);
}