Instructions
Splay基本操作
using namespace std;
struct Splay{
int data;
int ch[2];
int num;
int FA;
int size;
}t[maxn];
int newp;
void Rotate(int x){
int y=t[x].FA,z=t[y].FA,k=(t[y].ch[1]==x);//y是x的父亲,z是y的父亲(x的祖父),k是x是y的哪个儿子
t[z].ch[y==t[z].ch[1]]=x;//把x变到y原来的位置
t[x].FA=z;//把x的父亲变成z
t[y].ch[k]=t[x].ch[k^1];//把y原来是x的位置的变成x相对于y的位置
t[y].size=t[t[y].ch[k]].size+t[t[y].ch[k^1]].size;//把y的size更新
t[t[x].ch[k^1]].FA=y;//修改那个的父亲
t[x].ch[k^1]=y;//把x的相应儿子改成y
t[x].size==t[y].size+t[t[x].ch[k]].size;//更新x的size
t[y].FA=x;//把y的父亲改成x
}
void splay_S(int x,int destnation){
while(t[x].FA!=destnation){//如果没有把x旋成destnation的儿子
int y=t[x].FA,z=t[y].FA;//y父亲,z祖父
if(z!=destnation){//如果祖父还不是destnation
(t[z].ch[0]==y)^(t[y].ch[0]==x)?Rotate(x):Rotate(y);//如果共线旋y不共线旋x
}
Rotate(x);//无论共不共线都要旋x
}
if(destnation==0)root=x;//如果根节点是0那更新根节点
}
void find(x){//找到x的位置并且把x旋上去
int u=root;
if(!u)return;//如果是空树直接return
while(t[u].ch[x>t[u].data]&&x!=t[u].data){//如果还没有找到x的位置
u=t[u].ch[x>t[u].data];//如果x大于data就进右儿子否则进左儿子
}
splay_S(x,0);//把x旋上去
}
int Next_n(int x,bool flag){//寻找前驱||后继(flag==0是前驱,flag==1是后继)
find(x);//找到x的位置
int u=root;
if(t[u].data<x&&!flag)return u;//如果根节点比x小且是找前驱直接return u
if(t[u].data>x&&flag)return u;//如果根节点比x大且是找后继直接return u
u=t[u].ch[flag];//找前驱就找左儿子,后继就右儿子
while(t[u].ch[flag^1]){//当还没有遇到叶子结点的时候
u=t[u].ch[flag^1];//找前驱进入左儿子之后就找最右边的,找后继就进入右儿子之后找最左边的
}
return u;//返回前驱或者后继的位置
}
void insert(int x){
int u=root,fa=0;
while(u&&t[u].data!=x){//当还没有找到x或者还没有找到叶子结点的时候
fa=u;
u=t[u].ch[x>t[u].data];
}
if(u){//如果x已经存在
t[u].num++;//更新该结点的num
}
else{//否则
u=++newp;//重新建立一个结点
if(fa){//如果已经有父亲
t[fa].ch[x>t[fa].data]=u;//存成儿子
}
t[u].ch[0]=t[u].ch[1]=0;//新加的点是叶子结点没有儿子
t[u].FA=fa;//把父亲更新
t[u].data=x;//更新data
t[u].num=1;//更新num
t[u].size=1;//更新size
}
splay_S(u,0);//把该结点旋上去
}
void Delete_d(int x){//删除一个点
int Pre_x=Next_n(x,0);//找前驱
int Suc_x=Next_n(x,1);//找后继
splay_S(Pre_x,0);//把前驱旋到根节点
splay_S(Suc_x,Pre_x);//把后继旋到前驱
int del=t[Suc_x].ch[0];
if(t[del].cnt>1){//如果有多个该结点
t[del].cnt--;//删去一个
splay_S(del,0);//旋上去
}
else t[Suc_x].ch[0]=0;//否则直接删去这个点
}