传送门
一听是平衡树
就jio的很难很难
然而大佬说很简单
（听的时候确实jio的没有想象中的那么难<大佬讲的好orz）
然而
写代码的时候就完全不是了
足足花了我两个晚上啊
终于整的差不多明白了
（但我觉得我记不太住啊qwq）
（内疚...）
这是一个很优雅的平衡树！！！
什么是优雅呢！
暴力即优雅！！！
如果在一棵平衡的二叉搜索树内进行查询等操作
时间就可以稳定在log(n)
但是每一次的插入节点和删除节点
都可能会使得这棵树不平衡
最坏情况就是退化成一条链
显然我们不想要这种树
于是各种维护的方法出现了
大部分的平衡树都是通过旋转来维护平衡的
但替罪羊树就很厉害了
一旦发现不平衡的子树
立马拍扁重建
这就是替罪羊树的核心：暴力重建
那么
这个替罪羊树都支持那些操作呢？！
以下：（就是板子题中的那些）
插入x数
删除x数(若有多个相同的数，因只删除一个)
查询x数的排名(排名定义为比当前数小的数的个数+1+1+1。若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数)
求x的后继(后继定义为大于x，且最小的数)
代码小释：（这丑陋的拼音是我懒得改了，骂死我吧）
zuo,you：记录该节点的左右儿子
x：该节点的值
tot：有多少个值为x的数
size,trsize,whsize：size表示以该节点为根的子树内有多少个节点，trsize表示有多少个有效节点（这个后面再讲啦），whsize表示有多少个数（也就是子树内所有节点的tot的和）
fa：该点的父亲
tf：该点是否有删除标记（这个也会在后面讲啦
（个人认为自己272行的码风是极好的）
#include<cstdio>#include<cstring>struct node{int zuo,you,x,tot,size,trsize,whsize,fa;//tot表示x的个数；size表示以该节点为根的子树内有多少个节点//trsize表示有多少个有效节点，whsize表示有多少个数（也就是子树内所有节点的tot的和）bool tf;//该点是否有删除标记} tree[1000010];int len = 0,n,root = 0;int ck[1000010],t = 0;//ck数组为仓库，存下废弃的节点，t是ck数组的大小 double alpha = 0.75;//新建结点void build(int x,int y,int fa)//初始化树上编号为y的节点，它的值为x，父亲为fa{tree[y].zuo = tree[y].you = 0;tree[y].fa = fa;tree[y].tf = false;tree[y].x = x;tree[y].tot = tree[y].size = tree[y].trsize = tree[y].whsize = 1;//x的个数，子树的大小，有效的的数量，字数内所有点的tot值 均为一 }//神仙函数 inline int kk(){if(t > 0)return ck[t--];//假如仓库内有点，就直接用elsereturn ++len;//否则再创造一个点} //更新 void updata(int x,int y,int z,int k)//x为当前操作结点，y是有效节点增加的个数（trsize），z是子树增大的大小（size），k是数的个数增加的个数（whsize） {if(!x)//到头了就停止了 return; tree[x].trsize += y;tree[x].size += z;tree[x].whsize += k;updata(tree[x].fa,y,z,k);}//找点 int find(int x,int now)//now是当前找到的那个点,x是要找到的值 {if(x < tree[now].x && tree[now].zuo)return find(x,tree[now].zuo);if(x > tree[now].x && tree[now].you)return find(x,tree[now].you);return now;}//存数列的辅助结构体，就是子树拍扁后形成的那个数列 struct sl{int x,tot;}shulie[1000010];int tt;void dfs_rebuild(int x)//中序遍历，拍扁 {if(x == 0)//没有子树，结束 return;dfs_rebuild(tree[x].zuo);//先去左儿子if(!tree[x].tf)//假如没有删除标记，就只将他的x和tot加进数组，因为其他东西都没有用 {shulie[++tt].x = tree[x].x;shulie[tt].tot = tree[x].tot;}ck[++t] = x;//仓库，存下废弃的节点dfs_rebuild(tree[x].you); //再去右儿子} //把拍扁的数列变成树 int readd(int l,int r,int fa){if(l > r)return 0;int mid = (l + r)>>1;//中点即为子树的根 int id = kk();tree[id].fa = fa;tree[id].tot = shulie[mid].tot;tree[id].x = shulie[mid].x;tree[id].zuo = readd(l,mid-1,id);tree[id].you = readd(mid + 1,r,id);tree[id].whsize = tree[tree[id].zuo].whsize + tree[tree[id].you].whsize + shulie[mid].tot;tree[id].size = tree[id].trsize = r-l+1;tree[id].tf = false;return id; }//重建以x为根的子树void rebuild(int x){tt = 0;//数组下标 dfs_rebuild(x);if(x == root)root = readd(1,tt,0);else{updata(tree[x].fa,-tree[x].size+tree[x].trsize,0,0);if(tree[tree[x].fa].zuo == x)tree[tree[x].fa].zuo = readd(1,tt,tree[x].fa);elsetree[tree[x].fa].you = readd(1,tt,tree[x].fa);}}//重建（重新找根） 看看是否用拍扁 void find_rebuild(int now,int x)//now表示现在走到的节点，x表示要一直走到值为x的点 {if((double)tree[tree[now].zuo].size>(double)tree[now].size*alpha||(double)tree[tree[now].you].size>(double)tree[now].size*alpha||(double)tree[now].size-(double)tree[now].trsize>(double)tree[now].size*0.4){rebuild(now);return;}if(tree[now].x!=x)find_rebuild(x<tree[now].x?tree[now].zuo:tree[now].you,x);//继续向下搜索}//加点 void add(int x){if(root == 0){build(x,root = kk(),0);return;}int p = find(x,root);if(x == tree[p].x){tree[p].tot++;if(tree[p].tf){tree[p].tf = false;updata(p,1,0,1);}elseupdata(p,0,0,1);}elseif(x < tree[p].x){build(x,tree[p].zuo = kk(),p);updata(p,1,1,1);}else{build(x,tree[p].you = kk(),p);updata(p,1,1,1);}find_rebuild(root,x);} //删点void del(int x){int p = find(x,root);tree[p].tot--;if(!tree[p].tot){tree[p].tf = true;updata(p,-1,0,-1);}elseupdata(p,0,0,-1);find_rebuild(root,x);} //查询x数的排名 void findxpm(int x){int now = root;int ans = 0;while(tree[now].x != x){if(x < tree[now].x)now = tree[now].zuo;else{ans += tree[tree[now].zuo].whsize + tree[now].tot;now = tree[now].you;}}ans += tree[tree[now].zuo].whsize;printf("%d\n",ans+1);}//查询排名为x的数 void findpmx(int x){int now=root;while(1){if(x<=tree[tree[now].zuo].whsize)now=tree[now].zuo;else{x-=tree[tree[now].zuo].whsize;if(x<=tree[now].tot){printf("%d\n",tree[now].x);return;}x-=tree[now].tot;now=tree[now].you;}}}//求x的前驱int pre(int now,int x,bool zy){if(!zy)return pre(tree[now].fa,x,tree[tree[now].fa].zuo!=now);if(!tree[now].tf&&tree[now].x<x)return tree[now].x;if(tree[now].zuo){now=tree[now].zuo;while(tree[now].you)now=tree[now].you;return tree[now].x;}return pre(tree[now].fa,x,tree[tree[now].fa].zuo!=now);}//求x的后继 int nxt(int now,int x,bool zy){if(!zy)return nxt(tree[now].fa,x,tree[tree[now].fa].you!=now);if(!tree[now].tf&&tree[now].x>x)return tree[now].x;if(tree[now].you){now=tree[now].you;while(tree[now].zuo)now=tree[now].zuo;return tree[now].x;}return nxt(tree[now].fa,x,tree[tree[now].fa].you!=now);}int main(){scanf("%d",&n);while(n--){int id,x;scanf("%d %d",&id,&x);if(id==1)add(x);if(id==2)del(x);if(id==3)findxpm(x);if(id==4)findpmx(x);if(id==5)printf("%d\n",pre(find(x,root),x,true));if(id==6)printf("%d\n",nxt(find(x,root),x,true));}return 0; }
