首页 > 代码库 > Splay指针模板
Splay指针模板
#include<cstdio> #include<queue> #include<cstdlib> #define il inline struct node { int v; node* fa,ch[2]; }s[100045],*pos,*rt; il void newnode(node* &r,int v,node* fa) { if(mem.empty()) r=pos++; else r=mem.front(),mem.pop(); r->v=v; r->fa=fa; r->ch[0]=r->ch[1]=0; } il void roll(node* &r,boot t) { node* y=r->fa; if(y->fa) y->fa->ch[y->fa->ch[1]==y]=x; fa[x]=y->fa; if(x->ch[t]) x->ch[t]->fa=y; y->ch[!t]=x->ch[t]; x->ch[p]=y; y->fa=x; } il void splay(node* r,node* g)//将r旋转到g下面 { while(r->fa!=g) { if(r->fa->fa==g)//如果r的爸爸的爸爸就是目标 roll(r,r->fa->ch[0]==x->fa);//转一下就可以了 else {//自行理解,很简单 node* y=x->fa; bool t=y->fa->ch[0]==y; if(y->ch[0]==x) roll(y,t); else roll(x,!t); roll(x,t); } } if(!g)//目标没了,r当大爷 rt=r; } using namespace std; int main() { }
Splay指针模板
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。