Splay

# 没错这是神奇的平衡树（伸展树）QAQ  ## 来自Daniel Sleator 和 Robert Endre Tarjan的神奇科技  ### 先上板子哈 超详细的 题目为bzoj3224 [传送门](https://www.lydsy.com/JudgeOnline/problem.php?id=3224) ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+1e3+7; int num[N];//标号为x的相等数字 有num个 int sz[N];//此节点子树大小 int rev[N]; int fa[N],son[N][2];//当前点父亲 左儿子0||右儿子1 int rt;//根节点标号 int key[N];//当前点数值 int tot;//平衡树中节点数目 void update(int x) { sz[x]=sz[son[x][0]]+sz[son[x][1]]+num[x]; }//更新子树大小 （包括自己） void rotate(int x) { int y=fa[x],z=fa[y],t=(son[y][0]==x);//相当于是y&x在旋 但这个过程y x要换父亲 因此要引入z t用来自适应 if(z)//非根节点 son[z][son[z][1]==y]=x;//将z的某一个儿子设为x fa[x]=z;//连上 son[y][!t]=son[x][t];//相连最近儿子（左儿或右儿） fa[son[x][t]]=y; son[x][t]=y;//将y连到x下 fa[y]=x; update(y);//更新子树大小 update(x); } void splay(int x,int s)//当前节点 旋到何处结束 { while(fa[x]!=s)//即旋到x连到s下结束 { int y=fa[x],z=fa[y];//z为x的爷爷 y的父亲 if(z!=s)//控制边界 {//保证平衡树平衡 if((son[y][0]==x)^(son[z][0]==y))//x，y，z不在一条链上 rotate(x);//正常操作 else//否则折叠这个长链 rotate(y); } rotate(x);//双旋 上边的操作并未将当前点继续上传 因此要再转一下 } if(!s)//换根 即旋转到根结束 rt=x; } void insert(int &x,int s,int v)//插入：标号 祖先 数值 { if(!x)//为虚根节点 并且根节点只有一个 { x=++tot;//记录标号 fa[x]=s;//连到s下 key[x]=v;//保存这个数 sz[x]=num[x]=1;//子树大小和数据数都为1 son[x][0]=son[x][1]=0;//建上空的叶子节点 splay(x,0);//旋转至根节点 return; } if(num[x]>1)//此点数据数大于1 及是否存在 { sz[x]++; num[x]++;//子树大小和此点数据数都增加 splay(x,0);//旋转至根节点 return; } insert(son[x][v>key[x]],x,v);//如果前两个条件都不满足 则把它连上它的父亲 递归 update(x);//及时更新子树大小 } int get(int v)//找到数值为v的树上结点标号 { int x=rt; while(key[x]!=v&&x)//从根开始 x=son[x][v>key[x]];//通过逼近 找到比v小的（即v的左右儿子）其父亲即为所求 return x; } void del(int x)//删除某一值 { x=get(x); if(!x) return; splay(x,0);//旋转至根节点 if(num[x]>1) { num[x]--; sz[x]--; return; }//如果有很多 删去其中一个 并将num和sz更新 if(!son[x][0]||!son[x][1])//左右儿子其中一个不存在 rt=son[x][0]+son[x][1];//直接搞啊 反正一个是0 加上也无妨 else { int y=son[x][1];//右儿子 while(son[y][0])//如果有左儿子 y=son[y][0];//就一直向下 找到第一个比x大的数值所在节点 splay(y,x);//然后把y旋转至x son[y][0]=son[x][0];//把x的左儿子给y fa[son[x][0]]=y;//同上 rt=y;//把根搞成y } update(rt);//正经换根操作 fa[rt]=0;//同上 } int rank(int v)//找到数值为v的节点的排名 { int x=rt,ret=0;//此时先从根找 ret维护答案 while(x)//非虚根 { if(v<=key[x])//如果此数值≤当前数值 那么将x变成它的左儿子 即向左搜 x=son[x][0]; else { ret+=sz[son[x][0]]+num[x];//排名即为左儿子子树大小和左儿子的大小之和 x=son[x][1];//然后把它变成自己的右儿子 即向右搜 } } return ret+1;//加上自己 } int kth(int v)//查询排名为v的数 { int x=rt; while(v<=sz[son[x][0]]||v>sz[son[x][0]]+num[x]) { if(v<=sz[son[x][0]]) x=son[x][0]; else//若大于 则减一下 然后把x移到左儿子处 v-=sz[son[x][0]]+num[x],x=son[x][1]; } return key[x]; } int pre(int v)//前驱 第一个比v小的数值所在节点的数值 { int x=rt,ret=-0x7fffffff;//查询最小 因此此处赋值为负无穷 while(x) { if(v>key[x]) ret=max(ret,key[x]),x=son[x][1];//因为要在左子树一直向右下走 所以要取max else x=son[x][0];//否则自然要向左走 } return ret; } int suf(int v)//后继 第一个比v大的数值所在节点的数值 { int x=rt,ret=0x7fffffff;//查询最大 因此此处赋值为正无穷 while(x) { if(v<key[x]) ret=min(ret,key[x]),x=son[x][0];//因为要在右子树一直向左下走 所以要取min else x=son[x][1];//否则自然要向右走 } return ret; } int n; int main() { scanf("%d",&n); while(n--) { int op,x; scanf("%d%d",&op,&x); if(op==1) insert(rt,0,x);//加入 if(op==2) del(x);//删除 if(op==3) printf("%d\n",rank(x)); if(op==4) printf("%d\n",kth(x)); if(op==5) printf("%d\n",pre(x)); if(op==6) printf("%d\n",suf(x)); } } ``` ------------ ~~讲解待补~~