【bzoj3224】Tyvj 1728 普通平衡树 01Trie姿势+平衡树的四种姿势 ：splay，旋转Treap，非旋转Treap，替罪羊树

时间：2022-11-22 20:12:27

直接上代码 正所谓 人傻自带大常数

平衡树的几种姿势：  AVL Red&Black_Tree 码量爆炸，不常用；SBT 出于各种原因，不常用。

常用：

Treap 旋转 基于旋转操作和随机数堆 但不支持区间操作。

非旋转 基于随机数堆和拆分合并操作 常数较大

时间复杂度：很难被卡，均摊O（logN）

#include<cstdio>

#include<iostream>

#include<cstdlib>

#define MAXN 100005

using namespace std;

int ch[MAXN][],key[MAXN],r[MAXN],size[MAXN],cnt[MAXN],root,sz,n,m;

inline void update(int x)

{

   size[x]=size[ch[x][]]+size[ch[x][]]+cnt[x];

}

inline void rotate(int &x)

{

    int wh=r[ch[x][]]>r[ch[x][]],son=ch[x][wh];

    ch[x][wh]=ch[son][wh^];

    ch[son][wh^]=x;

    update(x);

    update(son);

    x=son;

}

void insert(int &now,int x)

{

    if(!now)

    {

       now=++sz;

       cnt[sz]=size[sz]=;

       key[sz]=x;

       r[sz]=(rand()%+rand());

       return;

    }

    if(key[now]==x)

    {

       cnt[now]++;

       size[now]++;

       return;

    }

    insert(ch[now][key[now]<x],x);

    if(r[now]<r[ch[now][key[now]<x]])

      rotate(now);

    else

      update(now);

}

void del(int &now,int x)

{

    if(key[now]==x)

    {

       if(cnt[now]>)

       {

         cnt[now]--;

         size[now]--;

         return;

       }

       if(ch[now][]*ch[now][]==)

       {

         now=ch[now][]+ch[now][];

         return;

       }

       rotate(now);

       del(ch[now][key[ch[now][]]==x],x);

       update(now);

       return;

    }

    del(ch[now][key[now]<x],x);

    update(now);

}

inline int kth(int x)

{

   int now=root;

   while()

   {

      if(size[ch[now][]]>=x)

      {

        now=ch[now][];

        continue;

      }

      int lon=cnt[now]+size[ch[now][]];

      if(lon>=x)

       return key[now];

      x-=lon;

      now=ch[now][];

   }

}

inline int rank(int x)

{

   int now=root,ans=;

   while()

   {

      if(key[now]==x)

        return ans++size[ch[now][]];

      if(x<key[now])

      {

         now=ch[now][];

         continue;

      }

      ans+=cnt[now]+size[ch[now][]];

      now=ch[now][];

   }

}

inline int pre(int x)

{

   int now=root,ans=-0x7fffffff;

   while(now)

   if(key[now]<x)

   {

      if(key[now]>ans)

       ans=key[now];

      now=ch[now][];

   }

   else

     now=ch[now][];

   return ans;

}

inline int next(int x)

{

   int now=root,ans=0x7fffffff;

   while(now)

   if(key[now]>x)

   {

      if(key[now]<ans)

       ans=key[now];

      now=ch[now][];

   }

   else

     now=ch[now][];

   return ans;

}

int main()

{

    freopen("phs.in","r",stdin);

    freopen("phs.out","w",stdout);

    scanf("%d",&n);

    while(n--)

    {

       int x,y;

       scanf("%d%d",&y,&x);

       switch(y)

       {

         case :insert(root,x);break;

         case :del(root,x);break;

         case :printf("%d\n",rank(x));break;

         case :printf("%d\n",kth(x));break;

         case :printf("%d\n",pre(x));break;

         case :printf("%d\n",next(x));break;

       }

    }

    return ;

}

旋转Treap

#include<cstdio>

#include<cstring>

#include<iostream>

#include<ctime>

#include<cstdlib>

#define MAXN 100010

using namespace std;

inline int read()

{

   int sum=,f=;

   char ch=getchar();

   while(ch<''||ch>'')

   {

       if(ch=='-')f=-;

       ch=getchar();

   }

   while(ch>=''&&ch<='')

   {

      sum=(sum<<)+(sum<<)+ch-'';

      ch=getchar();

   }

   return sum*f;

}

struct Treap

{

     struct Node

     {

        Node *ch[];

        int key,v,size;

        void pushup()

        {

           size=ch[]->size+ch[]->size+;

        }

     }null[MAXN],*root,*stack[MAXN];

     int top;

     void Init()

     {

        top=;

        root=null;

        null->ch[]=null->ch[]=null;

        for(int i=;i<MAXN;i++)stack[++top]=null+i;

     }

     Node *New(int key)

     {

        Node *p=stack[top--];

        p->ch[]=p->ch[]=null;

        p->size=;

        p->key=key;

        p->v=rand();

        return p;

     }

     Node *Merge(Node *a,Node *b)

     {

       if(a==null)return b;

       if(b==null)return a;

       if(a->v<b->v)

       {

          a->ch[]=Merge(a->ch[],b);

          a->pushup();

          return a;

       }

       else

       {

          b->ch[]=Merge(a,b->ch[]);

          b->pushup();

          return b;

       }

     }

     pair<Node*,Node*> split(Node *x,int k)

     {

         if(x==null)return make_pair(null,null);

         if(x->ch[]->size>=k)

         {

            pair<Node*,Node*> y=split(x->ch[],k);

            x->ch[]=y.second;

            x->pushup();

            y.second=x;

            return y;

         }

         else

         {

            pair<Node*,Node*> y=split(x->ch[],k-x->ch[]->size-);

            x->ch[]=y.first;

            x->pushup();

            y.first=x;

            return y;

         }

     }

     int getrank(Node *p,int key)

     {

          if(p==null)return ;

          return p->key>=key?getrank(p->ch[],key):getrank(p->ch[],key)+p->ch[]->size+;

     }

     int getkth(int k)

     {

          Node *now=root;

          while()

           if(now->ch[]->size>=k)

            now=now->ch[];

           else

            if(now->ch[]->size+==k)

             return now->key;

            else

             k-=now->ch[]->size+,now=now->ch[];

     }

     void insert(int key)

     {

          int k=getrank(root,key);

          pair<Node*,Node*> x=split(root,k);

          Node *p=New(key);

          root=Merge(Merge(x.first,p),x.second);

     }

     void del(int key)

     {

          int k=getrank(root,key);

          pair<Node*,Node*> x=split(root,k);

          pair<Node*,Node*> y=split(x.second,);

          stack[++top]=y.first;

          root=Merge(x.first,y.second);

     }

     int prefix(int key)

     {

          return getkth(getrank(root,key));

     }

     int suffix(int key)

     {

          return getkth(getrank(root,key+)+);

     }

}YY;

int main()

{

  freopen("phs.in","r",stdin);

    freopen("phs.out","w",stdout);

  YY.Init();

  int T=read();

  while(T--)

  {

      int opt=read();

      int x=read();

      switch(opt)

      {

         case :YY.insert(x);

                break;

         case :YY.del(x);

                break;

         case :printf("%d\n",YY.getrank(YY.root,x)+);

                break;

         case :printf("%d\n",YY.getkth(x));

                break;

         case :printf("%d\n",YY.prefix(x));

                break;

         case :printf("%d\n",YY.suffix(x));

                break;

      }

  }

  return ;

}

非旋转Treap

PS:非旋转可以实现平衡树的可持久化，还能来套一些东西

Spaly 完全基于旋转 各种操作

时间复杂度：引用：“ 称单旋无神犇，双旋O(logN)，这句话我也没有考证，个人表示不想做什么太多的探究”。毕竟Splay的复杂度本来就挺玄学的了，而且专门卡单旋Splay的题也没怎么听说过。

#include<cstdio>

#define MAXN 200005

using namespace std;

int key[MAXN],ch[MAXN][],cnt[MAXN],size[MAXN],f[MAXN],n,sz,root;

inline void clear(int x)

{

    key[x]=ch[x][]=ch[x][]=cnt[x]=size[x]=f[x]=;

}

inline int get(int x)

{

    return ch[f[x]][]==x;

}

inline void update(int x)

{

    size[x]=cnt[x]+size[ch[x][]]+size[ch[x][]];

}

inline void rotate(int x)

{

    int fa=f[x],pa=f[fa],what=get(x);

    if(pa){ch[pa][fa==ch[pa][]]=x;}

    ch[fa][what]=ch[x][what^];

    f[ch[fa][what]]=fa;

    ch[x][what^]=fa;

    f[fa]=x;

    f[x]=pa;

    update(fa);

    update(x);

}

inline void splay(int x)

{

    for(int fa;(fa=f[x]);rotate(x))

     if(f[fa])

      rotate((get(x)==get(fa)?fa:x));

    root=x;

}

inline void insert(int x)

{

    if(!root)

    {

       sz++;

       ch[sz][]=ch[sz][]=f[sz]=;

       key[sz]=x;

       cnt[sz]=size[sz]=;

       root=sz;

       return;

    }

    int now=root,fa=;

    while()

    {

       if(key[now]==x)

       {

          cnt[now]++;

          splay(now);

          return;

       }

       fa=now;

       now=ch[now][key[now]<x];

       if(!now)

       {

          sz++;

          f[sz]=fa;

          ch[sz][]=ch[sz][]=;

          key[sz]=x;

          cnt[sz]=;

          ch[fa][key[fa]<x]=sz;

          splay(sz);

          return;

       }

    }

}

inline void find(int x)

{

    int now=root;

    while()

    {

       if(x<key[now])

       {

         now=ch[now][];

         continue;

       }

       if(key[now]==x)

       {

         splay(now);

         return;

       }

       now=ch[now][];

    }

}

inline int rank(int x)

{

    find(x);

    return size[ch[root][]]+;

}

inline int findx(int x)

{

    int now=root;

    while()

    {

       if(size[ch[now][]]>=x)

       {

          now=ch[now][];

          continue;

       }

       int lon=size[ch[now][]]+cnt[now];

       if(x<=lon)

        return key[now];

       x-=lon;

       now=ch[now][];

    }

}

inline void del(int x)

{

    find(x);

    if(cnt[root]>){cnt[root]--;return;}

    if(size[root]==){clear(root);root=;return;}

    if (!ch[root][]){ int oldroot=root;root=ch[root][];f[root]=;clear(oldroot);return;

     }

     else if (!ch[root][]){

          int oldroot=root;root=ch[root][];f[root]=;clear(oldroot);return;

     }

    int now=ch[root][],old=root;

    while(ch[now][])now=ch[now][];

    f[ch[old][]]=now;

    ch[now][]=ch[old][];

    f[ch[old][]]=;

    clear(old);

    splay(now);

    return;

}

inline int pre(int x)

{

    insert(x);

    int now=ch[root][];

    while(ch[now][])now=ch[now][];

    del(x);

    return key[now];

}

inline int next(int x)

{

    insert(x);

    int now=ch[root][];

    while(ch[now][])now=ch[now][];

    del(x);

    return key[now];

}

int main()

{

    scanf("%d",&n);

    while(n--)

    {

       int x,y;

       scanf("%d%d",&y,&x);

       switch(y)

       {

         case :insert(x);break;

         case :del(x);break;

         case :printf("%d\n",rank(x));break;

         case :printf("%d\n",findx(x));break;

         case :printf("%d\n",pre(x));break;

         case :printf("%d\n",next(x));break;

       }

    }

    return ;

}

Splay

ScapeGoat_Tree 基于a权值平衡树和压扁重构 无旋转 但不支持区间操作；运用a权值平衡树一定是a高度平衡树来维持log的效率；主要操作就是拍扁重建，但是为了解决删除时的繁冗讨论所以维持一个带有已删除点的残树，维持这棵树的高度，同时在维护时维护这棵树的残点不超过一定比例；如果不用cnt那么删除时一定要用找排名的方式，这样的话会防止原来的一子链重建后成为人字链

时间复杂度：最坏会被卡到O（n2）（实际上∑(㏒₂n/i)*(㏒₂i)*i）（只是重建）但是那是把区间从大到小输入（或相反），实际上这是不加常数的结果（此处常数指替罪羊判断不平衡时除了alpha以外的那个常数），一般会是均摊logn(CTR会为了性命而不敢去卡)

#include<cstdio>

#include<iostream>

using namespace std;

const int MAXN=;

const double a=0.75;

struct node

{

    node *ch[];

    int key,size,cover,ex;

    inline void update()

    {

       size=ch[]->size+ch[]->size+ex;

       cover=ch[]->cover+ch[]->cover+;

    }

    inline bool bad()

    {

        return ch[]->cover>=cover*a+||ch[]->cover>=cover*a+;

    }

}Mem[MAXN],*null,*root,*stack[MAXN],*lst[MAXN];

int len,top;

inline void Init()

{

    root=null=Mem;

    null->size=null->cover=null->ex=;

    null->ch[]=null->ch[]=Mem;

    for(int i=;i<MAXN;i++)stack[++top]=Mem+i;

}

inline node *New(int key)

{

    node *t=stack[top--];

    t->ch[]=t->ch[]=null;

    t->size=t->cover=t->ex=;

    t->key=key;

    return t;

}

inline void travel(node *p)

{

    if(p==null)return;

    travel(p->ch[]);

    if(p->ex)lst[++len]=p;

    else stack[++top]=p;

    travel(p->ch[]);

}

inline node *divide(int l,int r)

{

    if(l>r)return null;

    int mid=(l+r)>>;

    lst[mid]->ch[]=divide(l,mid-);

    lst[mid]->ch[]=divide(mid+,r);

    lst[mid]->update();

    return lst[mid];

}

inline void rebuild(node *&p)

{

    len=;

    travel(p);

    p=divide(,len);

}

inline node **insert(node *&p,int key)

{

    if(p==null)

    {

        p=New(key);

        return &null;

    }

    p->size++;

    p->cover++;

    node **ret=insert(p->ch[p->key<=key],key);

    if(p->bad())ret=&p;

    return ret;

}

inline void erace(node *p,int k)

{

    //cout<<p->ch[0]->size<<endl;

    p->size--;

    if(p->ex&&k==p->ch[]->size+)

    {

        p->ex=;

        return;

    }

    if(k<=p->ch[]->size)erace(p->ch[],k);

    else erace(p->ch[],k-p->ch[]->size-p->ex);

}

inline int Kth(int k)

{

    node *p=root;

    while(p!=null)

    {

         if(p->ex&&k==p->ch[]->size+)return p->key;

         else if(p->ch[]->size>=k)p=p->ch[];

         else k-=p->ch[]->size+p->ex,p=p->ch[];

    }

}

inline int Rank(int x)

{

    node *p=root;

    int ret=;

    while(p!=null)

     if(p->key>=x)

      p=p->ch[];

     else

      ret+=p->ch[]->size+p->ex,p=p->ch[];

    return ret;

}

inline void Insert(int x)

{

    node **p=insert(root,x);

    if(*p!=null)rebuild(*p);

}

inline void Erace_kth(int k)

{

    erace(root,k);

    if(root->size<root->cover*a)rebuild(root);

}

inline void Erace(int x)

{

    Erace_kth(Rank(x));

}

int main()

{

    freopen("phs.in","r",stdin);

    freopen("phs.out","w",stdout);

    Init();

    int Q,opt,x;

    scanf("%d",&Q);

    while(Q--)

    {

        scanf("%d%d",&opt,&x);

        switch(opt)

        {

            case :Insert(x);break;

            case :Erace(x);break;

            case :printf("%d\n",Rank(x));break;

            case :printf("%d\n",Kth(x));break;

            case :printf("%d\n",Kth(Rank(x)-));break;

            case :printf("%d\n",Kth(Rank(x+)));break;

        }

    }

}

ScapeGoat——Tree

打了四种平衡树，发现01Trie最快还™短..........

#include <cstdio>

using namespace std;

const int A=,fix=;

inline void read (int &now){

    register char word=getchar();bool temp=false;

    for(now=;word<''||word>'';word=getchar())if(word=='-')temp=true;

    for(;word>=''&&word<='';now=(now<<)+(now<<)+word-'',word=getchar());

    if(temp)now=-now;

}

struct Trie{

  Trie *ch[];int size;

  void* operator new(size_t);

}*root,*null,*C,*mempool;

void* Trie :: operator new(size_t){

  if(C==mempool)C=new Trie[(<<)+],mempool=C+(<<)+;

  return C++;

}

inline Trie *New(){

  register Trie *p=new Trie;

  p->ch[]=p->ch[]=null,p->size=;

  return p;

}

int n;

inline void Insert(int x,int size){

  register Trie *p=root;x+=fix;

  for(int i=A;i>=;i--){

    if(p->ch[(x>>i)&]==null)p->ch[(x>>i)&]=New();

    p=p->ch[(x>>i)&];p->size+=size;

  }

}

inline int get_Rank(int x){

  register int ret=;x+=fix;register Trie *p=root;

  for(register int i=A;i>=&&p!=null;i--)

    if(x&(<<i))ret+=p->ch[]->size,p=p->ch[];

    else p=p->ch[];

  return ret;

}

inline int get_Kth(int k){

  register Trie *p=root;register int ret=;

  for(register int i=A;i>=;i--)

    if(p->ch[]->size>=k)p=p->ch[];

    else ret|=(<<i),k-=p->ch[]->size,p=p->ch[];

  return ret-fix;

}

int main(){

  freopen("phs.in","r",stdin);freopen("phs.out","w",stdout);

  null=new Trie,null->ch[]=null->ch[]=null,null->size=,root=new Trie,root->ch[]=root->ch[]=null,root->size=;

  read(n);register int opt,x;

  while(n--){

    read(opt),read(x);

    switch(opt){

      case :Insert(x,);break;

      case :Insert(x,-);break;

      case :printf("%d\n",get_Rank(x)+);break;

      case :printf("%d\n",get_Kth(x));break;

      case :printf("%d\n",get_Kth(get_Rank(x)));break;

      case :printf("%d\n",get_Kth(get_Rank(x+)+));break;

    }

  }

}

01Trie

相关文章