题解 P3369 【【模板】普通平衡树】

Starlight237 · 2020-01-26 15:39:41 · 题解

为何整个题解区都没有指针Splay？指针版Splay的常数几乎可以和WBLT相媲美，而且在构造数据上表现十分优越，甚至比一般的treap和SBT要快。

然而众所周知，指针版Splay并不是那么好写我调了一上午，故发一篇题解提供参考，顺便指出几个需要注意的地方。

口胡完毕，下面进入正题

key points

1.关于空指针

• 众所周知，有一种十分烦人的指针，叫做空指针（NULL）。在树形数据结构中，我们常常会不可避免地访问到空指针（例如一个节点只有右儿子，我们却访问了它的左儿子）。通常的方式是凡是访问了指针，都判断一下。然而这样效率十分低下，大量分支的存在使得代码冗长，常数变大，不易调试，可读性降低等问题。
• 我们可以考虑新开一个节点Node *null;来表示空指针。这样，即使我们遇到了一个为空的指针rt，并且试图访问rt->siz（应当为0），也不用担心会出现RE or WA。
• 写代码时一定要注意节点的初始化，切不可有可能被访问到的指针为空却没有被赋为null的情况。
• null节点指向的对象不应当在任何时候被修改。

2.数组要开大，因为有null这样的多余指针。建议至少开到maxn+3（笔者采用maxn+10）。

3.和WBLT不同，root不可以被初始化，而是应当被赋为null。因为我们插入第一个数值时，这个数值应当被放在root。

4.针对各个函数的其他key points参见注释。需要注意的是，代码使用了内存池，删除节点会回收内存。

5.关于码风

• 为了卡常数（而不是压行）略有些毒瘤。三目就不说了，然后a&&(b,0)这样的东西表示if(a)b;而a||(b,0)表示if(!a)b;这里用了短路运算的特点。

  code

  
  #include<bits/stdc++.h>
  using namespace std;
  #define reg register
  extern "C"{
  namespace io{
  #define IOSIZE 1000000
  static char in[IOSIZE],*p=in,*pp=in,out[IOSIZE],*q=out,ch[20],*t=ch;
  inline char gc(){return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?EOF:*p++;}
  inline int read(){
      reg int x=0;reg char f=0,ch;
      while(!isdigit(ch=gc()))f|=ch=='-';
      while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();
      return f?-x:x;
  }
  inline void write(int x){
      x||(*q++=48),x<0&&(*q++='-',x=-x);
      while(x)*t++=x%10+48,x/=10;
      while(t!=ch)*q++=*--t;
      *q++='\n';
  }
  inline void flush(){fwrite(out,1,q-out,stdout);}
  }}
  #define rd io::read
  #define wt io::write
  const int N=100010;
  inline void work();
  int main(){
  work();
  io::flush();
  return 0;
  }
  //End of MAIN
  int n;
  namespace Splay{
  struct Node{
      int v,cnt,siz;Node *fa,*ch[2];
      Node(){}
      Node(int V,int Cnt,int Siz,Node *Fa,Node *ls,Node *rs):
      v(V),cnt(Cnt),siz(Siz),fa(Fa){ch[0]=ls,ch[1]=rs;}
  }*null,tr[N],*pl[N],**ptr=pl,*root;
  #define newNode(a,b,c,d,e,f) (&(**ptr++=Node(a,b,c,d,e,f)))
  inline void init(){
      for(reg int i=0;i<N;++i)pl[i]=&tr[i];//初始化内存池
      null=newNode(0,0,0,0,0,0),root=null;//空节点与根
  }
  inline void pushup(Node *rt){
      rt->siz=rt->ch[0]->siz+rt->ch[1]->siz+rt->cnt;
  }
  #define connect(a,b,son) (b->ch[son]=a,a->fa=b,0)
  inline void rotate(Node *x){
      reg Node *y=x->fa,*z=y->fa;reg int k=y->ch[1]==x;
      connect(x->ch[k^1],y,k),connect(y,x,k^1),
      z!=null?connect(x,z,z->ch[1]==y):(x->fa=z,0);//此处应当判断z指针是否空。因为null指针不应当被修改。
      pushup(y),pushup(x);
  }
  inline void splay(Node *x,Node *g){
      for(reg Node *y,*z;x->fa!=g;rotate(x))
          y=x->fa,z=y->fa,
          z!=g&&(rotate((y->ch[0]==x)^(z->ch[0]==y)?x:y),0);
      g==null&&(root=x,0);
  }
  inline void ins(int x){
      reg Node *rt=root,*ff=null;
      for(;rt!=null&&rt->v!=x;ff=rt,rt=rt->ch[x>rt->v]);
      if(rt!=null){++rt->cnt,splay(rt,null);return;}//判断根节点是否为空
      rt=newNode(x,1,1,ff,null,null),ff!=null&&(ff->ch[x>ff->v]=rt,0);//新加入节点。rt的左右儿子是空的，因此应当被赋为null。
      splay(rt,null);
  }
  inline void Find(int x){
      reg Node *rt=root;if(rt==null)return;
      for(;rt->ch[x>rt->v]!=null&&rt->v!=x;rt=rt->ch[x>rt->v]);
      splay(rt,null);
  }
  inline Node *Nxt(int x,int op){
      Find(x);
      reg Node *rt=root;
      if(rt->v>x&&op||rt->v<x&&!op)return rt;
      rt=rt->ch[op];
      for(;rt->ch[op^1]!=null;rt=rt->ch[op^1]);
      return rt;
  }
  inline void del(int x){
      reg Node *lst=Nxt(x,0),*nxt=Nxt(x,1);
      splay(lst,null),splay(nxt,lst);
      reg Node *tmp=nxt->ch[0];
      tmp->cnt>1?--tmp->cnt,splay(tmp,null),0:(*--ptr=tmp,nxt->ch[0]=null,0);//三目。注意这里回收了内存。
  }
  inline int kth(int k){
      reg Node *rt=root,*y;
      if(rt->siz<k)return 0;
      for(;;){
          y=rt->ch[0];
          if(y->siz+rt->cnt<k){k-=y->siz+rt->cnt,rt=rt->ch[1];continue;}
          if(y->siz>=k){rt=y;continue;}
          return rt->v;
      //为了优化常数，所有else被删去，并用continue代替。
      }
  }
  }
  inline void work(){
  n=rd();
  Splay::init();
  Splay::ins(2147483647),Splay::ins(-2147483648);//记得初始化
  for(reg int i=1,x,y;i<=n;++i)
      switch(y=rd(),x=rd(),y){
          case 1:Splay::ins(x);break;
          case 2:Splay::del(x);break;
          case 3:
              Splay::Find(x),wt(Splay::root->ch[0]->siz);
              break;
          case 4:wt(Splay::kth(x+1));break;//记得+1
          case 5:wt(Splay::Nxt(x,0)->v);break;
          case 6:wt(Splay::Nxt(x,1)->v);break;
      }
  }