首页 > 代码库 > 【整合】Splay模板
【整合】Splay模板
用了两天时间学了Splay+搞自己的模板
最后应该算是搞完了吧。
虽然可能还是有很多不太完美的地方OTZ
总感觉单纯维护集合还是sbt更好用QUQ(要不是为了做区间才不学Splay呢!)
指针各种难调试啊OTZ
一个remove调了一天(╯‵□′)╯︵┻━┻
以后除非是区间否则坚决不想用的东西(常数还比sbt大那么多=0=)
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define P 1000000 #define MAXINT 100000000000 using namespace std; struct splay { splay *ch[2],*fa;//ch[0]为左子树ch[1]为右子树fa为父节点 int data,cnt,size;//data节点数值cnt重复元素个数size树的大小 }*root,*no; int ans; int n,key,flag,pet,human; void calc(splay *x) { x->size=x->cnt; if (x->ch[0]) x->size+=x->ch[0]->size; if (x->ch[1]) x->size+=x->ch[1]->size; } void rot(splay *x,bool flag)//flag=0左旋flag=1右旋 节省编程复杂度的小优化 { splay *y=x->fa; y->ch[!flag]=x->ch[flag]; if (x->ch[flag]!=NULL) x->ch[flag]->fa=y; x->fa=y->fa; if (y->fa!=NULL) if (y->fa->ch[0]==y) y->fa->ch[0]=x; else y->fa->ch[1]=x; x->ch[flag]=y; y->fa=x; if (y==root) root=x; } void Splay(splay *x,splay *f)//将节点X提到节点f下 (地位与sbt Maintain()相同的操作0-0) { if (x==f||x==NULL) return; while (x->fa!=f) { if (x->fa->fa==f) { if (x->fa->ch[0]==x) rot(x,1); else rot(x,0); } else { splay *y=x->fa,*z=y->fa; if (z->ch[0]==y) if (y->ch[0]==x) rot(y,1),rot(x,1); else rot(x,0),rot(x,1); else if (y->ch[0]==x) rot(x,1),rot(x,0); else rot(y,0),rot(x,0); } } if (f==NULL) root=x; if (x!=NULL)calc(x); if (f!=NULL)calc(f); } void insert(int data) { splay *n=root,*x=NULL; while (n!=NULL) { x=n; if (data>=n->data) n=n->ch[1]; else n=n->ch[0]; } n=new splay; n->ch[0]=n->ch[1]=NULL; n->size=1; n->data=http://www.mamicode.com/data;>【整合】Splay模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。