splay板子

解锁新技能，伸展树，splay基于平衡二叉树，可以查询前驱和后继，保证差值最小哦

以x为主人公

右旋
无图（自行脑补qaq）

y节点为x节点的父节点，z节点为y节点的父节点（前置）
1.如果x节点存在右节点，那么就把它作为y节点的左儿子，更新x的右儿子的父亲为y节点。
void right_rotate(int x){
  int y=fa[x];
  int z=fa[y];
  fa[rightson[x]]=y;
  if (rightson[x]) {
       leftson[y]=rigthson[x]; 
      }

2.如果存在z且z为y的左儿子，那么x就为y的左儿子，更新
 if（z） {
   if (y==leftson[z]) leftson[z]=x;
   else rightson[z]=x;//这个地方对照一下操错了QAQ
 }
3.将y作为x的右子树
rightson[x]=y;
fa[y]=x;
}

左旋操作

left_rotate(int x)
{
  int y=fa[x];
  int z=fa[y];
  fa[leftson[x]]=y;
  if (leftson[x]）{
     rightson[y]=fa[leftson[x]];
  }
  if (z){
    if (rightson[z]==y) rightson[z]=x;
    else leftson[z]=x;
  }
  //将y作为x的左子树
leftson[x]=y;
fa[y]=x;
}

差不多辽，接下来上splay

void splay(int ancestry){
	while (fa[x]!=ancestry){
		int y=fa[x];
		int z=fa[y];
		if (z==ancestry){
			if (rightson[y]==x) left_rotate(x);
			else right_rotate(x);
		}
		else {
			if (rightson[z]==y&&rightson[y]==x) {
				left_rotate(y);left_rotate(x);
			}
		   else if (leftson[z]==y&&leftson[y]==x)
		       {
		       	right_rotate(y);right_rotate(x);
			   }
		   else if (leftson[z]==y&&rightson[y]==x) 
		        {
		        	right_rotate(y);
		        	left_rotate(x);
				}
			else if (rightson[z]==y&&leftson[y]==x)
			  {
			  	  left_rotate(y);
			  	  right_rotate(x);
			  }
		}
	}
	if (ancestry==0) root=x;
}