splay模板随手记
实现splay操作：
序言：
OiWiki传送门
一：初始操作
1.初始化：
int rt,id;
//树根和总节点编号
int f[N],ch[N][2],val[N];
//父亲，左右儿子，值
int cnt[N],sz[N];
//副本数，子树大小 2.判左右儿子：
右儿子为1.左儿子为0
inline bool dir(int x){
return x==ch[f[x]][1];
}3.单点更新子树大小：
注意：一个节点的子树大小表示其左子树大小，右子树大小和此节点副本数之和
inline void push_up(int x){
sz[x]=cnt[x]+sz[ch[x][0]]+sz[ch[x][1]];
}4.单旋操作（zig,zag融合）：
inline void rotate(int x){
int y=f[x],z=f[y];//y为x父亲，z为x祖父
bool r=dir(x);
ch[y][r]=ch[x][!r];//y代表x的子树连接x的另一子树
ch[x][!r]=y;//x的另一子树更新为y
if (z) ch[z][dir(y)]=x;
//如果x有祖父节点，让x取代原y位置
if (ch[y][r]) f[ch[y][r]]=y;
//如果y原来代表x的子树位置现有子树，让子树认y做父亲
//第四行已经更新儿子关系，未更新父亲关系
f[y]=x;f[x]=z;
//让y反认父亲，让x认祖父当父亲（取代y节点位置）
push_up(y);//更新y子树关系
push_up(x);//更新x子树关系
}5.splay伸展操作（将x旋转到根）：
-
一步到根只需转x
-
(1) x和y同侧：则需要zig-zig（先转y再转x）  (2) x和y异侧：则需要zig-zag（转两次x） 
inline void splay(int& z,int x){
//z为根节点，x为上旋节点
int w=f[z];//设w为根节点z的父亲（当x的父亲为w时，x就是根了）
for (int y;(y=f[x])!=w;rotate(x))//y是x父亲
if (f[y]!=w)//当旋转操作还差>=2步到根时
rotate(dir(x)==dir(y)?y:x);
//当x和y同为左/右子树启用zig-zig（转y 转x）
//当x和y左右子树性质不同用zig-zag（转x 转x）
//当旋转操作只差一步到根时只需旋转x到根
z=x;//把z（即rt）更新为x
}