Flandre_Scarletsplay

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
void rotate(int x) {
    int y=f[x].pre,z=f[y].pre;
    if (f[y].l==x) {
        f[y].l=f[x].r;
        f[x].r=f[f[x].r].pre=y;
    }
    else {
        f[y].r=f[x].l;
        f[x].l=f[f[x].l].pre=y;
    }
    update(y);update(x);
    f[y].pre=x;f[x].pre=z;
    if (z>0) 
        if (f[z].l==y) f[z].l=x;
        else f[z].r=x;
}   

int splay(int x,int now) {
    while (f[x].pre!=now) {
        int y=f[x].pre,z=f[y].pre;
        if (z!=now)
            if ((f[z].l==y)&&(f[y].l==x)||(f[z].r==y)&&(f[y].r==x)) rotate(y); else rotate(x);
        rotate(x);
    }
}
}}}
{{{
//这是CLJ神犇的splay
struct node
 {
  int k,s;
  bool d,rev;
  node*c[2],*p;
  node(){c[0]=c[1]=p=0;}
  void sc(node*_c,bool d)
  {c[d]=_c;_c->p=this;_c->d=d;}

 void rot(Node t)
 {
  Node p=t->p;
  pus(p);pus(t);bool d=t->d;
  p->sc(t->c[!d],d);
  p->p->sc(t,p->d);
  t->sc(p,!d);
  upd(p);upd(t);
  if(p==root) root=t;
 }
 void spl(Node x,Node f)
 {
  for(pus(x);x->p!=f;)
  {
   if(x->p->p==f) rot(x);
   else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );  
  }  
 }

}}}

void rotate(int x) {
    int y=f[x].pre,z=f[y].pre;
    if (f[y].l==x) {
        f[y].l=f[x].r;
        f[x].r=f[f[x].r].pre=y;
    }
    else {
        f[y].r=f[x].l;
        f[x].l=f[f[x].l].pre=y;
    }
    update(y);update(x);
    f[y].pre=x;f[x].pre=z;
    if (z>0) 
        if (f[z].l==y) f[z].l=x;
        else f[z].r=x;
}   
int splay(int x,int now) {
    while (f[x].pre!=now) {
        int y=f[x].pre,z=f[y].pre;
        if (z!=now)
            if ((f[z].l==y)&&(f[y].l==x)||(f[z].r==y)&&(f[y].r==x)) rotate(y); else rotate(x);
        rotate(x);
    }
}

//这是CLJ神犇的splay
struct node
 {
  int k,s;
  bool d,rev;
  node*c[2],*p;
  node(){c[0]=c[1]=p=0;}
  void sc(node*_c,bool d)
  {c[d]=_c;_c->p=this;_c->d=d;}
 void rot(Node t)
 {
  Node p=t->p;
  pus(p);pus(t);bool d=t->d;
  p->sc(t->c[!d],d);
  p->p->sc(t,p->d);
  t->sc(p,!d);
  upd(p);upd(t);
  if(p==root) root=t;
 }
 void spl(Node x,Node f)
 {
  for(pus(x);x->p!=f;)
  {
   if(x->p->p==f) rot(x);
   else x->d==x->p->d?( rot(x->p),rot(x) ):( rot(x),rot(x) );  
  }  
 }