【洛谷P3369】普通平衡树（splay）

emmmmm直接丢代码了

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<set> #include<map> #include<queue> #include<algorithm> #include<vector> #include<cstdlib> #include<cmath> #include<ctime> #include<stack> #define ri register int using namespace std; const int mx = 100000 + 5; struct in {int sz,cnt,v;in *ch[2],*f;void su()//统计大小 {sz = ch[0] -> sz + ch[1] -> sz + cnt;}int dir()//判断自己为左/右蛾子 {return f -> ch[1] == this;}int cmp(int x)//判断该向哪里走 {if(v == x)return -1;return x > v;}void setc(in *p,int d)//把这棵子树接到另一个点上 {(ch[d] = p) -> f = this;} }T[mx],*root,*null,*Null; int tot; in* newnode(in *p,int x)//建立新节点 {in *qwq = &T[++ tot];qwq -> v = x,qwq -> f = p,qwq -> cnt = qwq -> sz = 1;qwq -> ch[0] = qwq -> ch[1] = Null;return qwq; } void rotate(in *p)//旋转 {in *fa = p -> f;int d = p -> dir();//判断旋转方向:d^1 fa -> f -> setc(p,fa -> dir());//先把p接到它父亲的位置上 fa -> setc(p -> ch[d ^ 1],d),fa -> su();//然后把这个多出来的蛾子接到原来p在fa的位置上 p -> setc(fa,d ^ 1),p -> su();//最后把fa接在d^1这边 if(root == fa)//判断是不是更新根节点 root = p; } void splay(in *p,in *rt) {if(rt == p)return ;while(p -> f != rt){if(p -> f -> f == rt){rotate(p);break;}else{if(p -> dir() == p -> f -> dir())//如果同方向，先旋转父亲，再旋转本身 rotate(p -> f),rotate(p);else//否则一直旋转本身 rotate(p),rotate(p);}}p -> su();if(rt == null)//如果发现这个点被要求旋转到树根，则更新树根 root = p; } void insert(in *p,int x)//插入 {if(root == Null)//如果一个点都没有 {root = newnode(null,x);return;//null是树根，Null是空的意思 }while(p -> ch[p -> v < x] != Null)//不停的走，x偏小向左，偏大向右，与该点相等停下 {if(p -> v == x)break;p = p -> ch[p -> v < x];}if(p -> v == x)//判断下是不是与该点相等 {p -> sz ++,p -> cnt ++,splay(p,null);return;}p -> ch[p -> v < x] = newnode(p,x);//建新点 splay(p -> ch[p -> v < x],null);//只要是插入删除就splay一下维持平衡 } in* find(int x)//查找一个点并返回它的位置 {in *rt = root;while(rt -> ch[x > (rt -> v)] != Null && x != (rt -> v))rt = rt -> ch[x > (rt -> v)];return rt; } in* next(int x,bool flag)//查找前驱后继 {in *rt = root,*qwq;int re;if(!flag)//前驱 {re = 0;while(rt -> ch[0]||rt -> ch[1]){if(rt -> v >= x){if(rt -> ch[0] != Null)//太大向左走 rt = rt -> ch[0];elsebreak;}else{if(rt -> v > re)//选取尽可能和x接近的数 re = rt -> v,qwq = rt;if(rt -> ch[1] != Null)//太小向右走 rt = rt -> ch[1];elsebreak; }}if(rt -> v < x && rt -> v > re)//与最后到达的点进行比较 re = rt -> v,qwq = rt;}else//后继，与前驱原理类似 {re = 1000000007;while(rt -> ch[0]||rt -> ch[1]){if(rt -> v <= x){if(rt -> ch[1] != Null)rt = rt -> ch[1];elsebreak;}else{if(rt -> v < re)re = rt -> v,qwq = rt;if(rt -> ch[0] != Null)rt = rt -> ch[0];elsebreak; }}if(rt -> v > x && rt -> v < re)re = rt -> v,qwq = rt;}return qwq; } void erase(int x)//删除 {in *rt = find(x);//先找到这个点 if(rt -> cnt > 1)//如果这个点上的数出现了很多次，就cnt-- {rt -> sz --,rt -> cnt --,splay(rt,null);return;}//否则把这个点彻底删除掉 bool k = rt -> f -> ch[1] == rt;//判断该点是右蛾子还是左蛾子 if(rt -> ch[0] == Null)if(rt -> ch[1] ==Null)//啥蛾子没有就直接删掉这个点 rt -> f -> ch[k] = Null;else//如果只有一个蛾子就让它代替被删除点的位置 rt -> f -> ch[k] = rt -> ch[1],rt -> ch[1] -> f = rt -> f;elseif(rt -> ch[1] == Null)rt -> f -> ch[k] = rt -> ch[0],rt -> ch[0] -> f = rt -> f;else//否则如果左右蛾子都有的话 ，就让左蛾子顶替位置，然后把右蛾子放到左蛾子子树的最靠上的右空位（因为右蛾子的任何一个点都比做蛾子大，肯定在这棵子树的最右边） {in *ls = rt -> ch[0];rt -> f -> ch[k] = rt -> ch[0];rt -> ch[0] -> f = rt -> f;while(ls -> ch[1] != Null)ls = ls -> ch[1];ls -> ch[1] = rt -> ch[1];rt -> ch[1] -> f =ls;ls -> su(),splay(ls,null);}rt -> f -> su();splay(rt -> f,null); } int ask(int x)//查找一个数的排名，利用二叉搜索树本身左小右大的性质 {if(root == Null)return 0;in *rt = root;int re = 0;while(rt -> v != x)//直到找到这个数为止 {bool fl = x > rt -> v;if(fl == 1)re += rt -> ch[0] -> sz + rt -> cnt;rt = rt -> ch[fl];}re += rt -> ch[0] -> sz + 1;//最后记录下左子树的大小然后再加上它本身 splay(rt,null);return re; } int ask1(int x)//查找排x位的数 {in *rt = root;int num = rt -> ch[0] -> sz;while(!(x > num && x <= num + rt -> cnt))//括号里面表达式的意思为恰好找到排名为k的时候 {if(x > num)//如果大于左子树，向右走，减去左侧排名 x -= num + rt -> cnt,rt = rt -> ch[1];else//否则向左走 rt = rt -> ch[0];num = rt -> ch[0] -> sz;}splay(rt,null);return rt -> v; } int n,opt,xx; int main() {Null = root = &T[++ tot],null = &T[++ tot],null -> ch[0] = null -> ch[1] = Null;//Null是为了初始赋值,null是根节点 scanf("%d",&n);while(n --){scanf("%d%d",&opt,&xx);if(opt == 1)insert(root,xx);//插入 if(opt == 2)erase(xx);//删除 if(opt == 3)printf("%d\n",ask(xx));//查询x的排名 if(opt == 4)printf("%d\n",ask1(xx));//查询排名为x的数 if(opt == 5)printf("%d\n",next(xx,0) -> v);//前驱 if(opt == 6)printf("%d\n",next(xx,1) -> v);//后继 } }

 

转载于:https://www.cnblogs.com/Loi-dfkdsmbd/p/8449498.html

总结

以上是生活随笔为你收集整理的【洛谷P3369】普通平衡树（splay）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。