我太菜了，平衡树板子打一遍忘一遍，重新学会了之后还要蛙上几次……

所以我整理了这个东西，希望能给将来的自己和一些其他的同学一些帮助。

1: 关于 build_tree

如果你在 build_tree 的过程中存了当前的区间和 father，那么在主函数调用 build_tree 的时候要注意：

不能写成： build_tree(0,n+1,1);

建议写成：build_tree(0,n+1,0);

前者之所以错误，是因为我们加入平衡树的第一个点的编号是 $1$，而 $rt$ 也是 $1$，这么一来一回 $1$ 的父节点就是 $1$。那么，在 Rotate 和 Splay 的过程中可能就会出现死循环的问题。

2: 关于 search

在模拟翻转 $[l,r]$ 的时候，你肯定要先把维护位置 $l-1$ 和 $r+1$ 的节点分别 Splay 上去，所以你必须要先在平衡树上定位到这两个位置。这就需要用到查询平衡树上排名为 $k$ 的节点的函数了。

记得，一定要在这个函数的运行过程中不停地做 pushdown。

3: 关于 Rotate

直接放代码吧，千万要注意 pushup 和 pushdown 的位置。

void Rotate(int x){
	int y=f[x],z=f[y],t=ge(x);
	pushdown(y),pushdown(x);//attention
	Connect(y,tree[x][t^1],t);
	Connect(x,y,t^1);
	Connect(z,x,tree[z][1]==y);
	pushup(y),pushup(x);//attention
}

刚开始 pushdown 是为了在 $x,y$ 的信息被 Rotate 打乱之前先把先前的标记下放到不会动的地方，结束之后 pushup 是为了在 $x,y$ 周围的环境改变了之后去更新节点上的信息。并且还要注意，一对 pushdown 的位置不能交换，一对 pushup 的位置也不能交换，毕竟没有先更新父亲的信息再更新儿子信息的道理，不然儿子的信息就传不到父亲那里去了。

void Rotate(int x){
	int y=f[x],z=f[y],t=ge(x);
	pushdown(y),pushdown(x);
	Connect(y,tree[x][t^1],t);
	Connect(x,y,t^1);
	Connect(z,x,tree[z][1]==y);
	pushup(y),pushup(x);
}

4: 关于 root

平衡树的 $root$ 会不停地改变，毕竟每次询问你都会把节点旋转上去，可能会作为新的根。所以，在每次 Splay 结束之后，一定要加上一行，来判断 $root$ 是不是已经被替换掉了；如果被替换掉了，就赶快把 $root$ 改掉。

此外，在最终 print_tree 的时候，一定要从 $root$ 出发，而不能从 $1$ 出发做中序遍历。总而言之，就是不要把 $root$ 和 $1$ 搞混淆了。