脑洞大开加偏执人格——可持久化treap版的Link Cut Tree

　　一直没有点动态树这个科技树，因为听说只能用Splay，用Treap的话多一个log。有一天脑洞大开，想到也许Treap也能从底向上Split。仔细思考了一下，发现翻转标记不好写，再仔细思考了一下，发现还是可以写的，只需要实时交换答案二元组里的两棵树，最后在吧提出来的访问节点放回去就行了。本着只学一种平衡树的想法，脑洞大开加偏执人格的开始写可持久化Treap版的Link Cut Tree。。。

　　写了才发现，常数硕大啊！！！代码超长啊！！！因为merge是从上到下，split从下到上，pushdown要写两个啊！！Link Cut Tree巧妙运用Splay特性将最左和最右提取之后合并是O(1)的呀！！Treap还要merge一次常数++啊。我冤枉啊！我只是不想学Splay啊！！好吧，我还是把它写出来了。。。

题目：洞穴探测

代码：

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 int father[];

 struct node

 {

     int num;

     int key;

     int left;

     int right;

     node* ls;

     node* rs;

     bool turn;

     node* f;

     node()

     {

         key=rand();

         f=NULL;

     }

 }no[];

 int root;

 void swap(node** a,node** b)

 {

     node* c=*a;

     *a=*b;

     *b=c;

 }

 void swap(int* a,int *b)

 {

     int c=*a;

     *a=*b;

     *b=c;

 }

 void pushdown(node* now)

 {

     if (now->turn)

     {

         swap(&now->ls,&now->rs);

         if (now->ls)

         {

             now->ls->turn=!now->ls->turn;

             swap(&now->ls->left,&now->ls->right);

         }

         if (now->rs)

         {

             now->rs->turn=!now->rs->turn;

             swap(&now->rs->left,&now->rs->right);

         }

     }

     now->turn=false;

 }

 void update(node* now)

 {

     now->left=now->right=now->num;

     if (now->ls)

         now->left=now->ls->left;

     if (now->rs)

         now->right=now->rs->right;

 }

 node* merge(node* a,node* b)

 {

     if (!a) {update(b);return b;}

     if (!b) {update(a);return a;}

     pushdown(a);

     pushdown(b);

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

     {

         a->rs=merge(a->rs,b);

         a->rs->f=a;

         update(a);

         return a;

     }

     else

     {

         b->ls=merge(a,b->ls);

         b->ls->f=b;

         update(b);

         return b;

     }

 }

 struct nodepair

 {

     node* l;

     node* r;

     nodepair(node* a,node* b)

     {

         l=a;

         r=b;

     }

 };

 nodepair pushdown(node* now,bool lr,nodepair ret)

 {

     now->turn=false;

     if (lr&&now->ls)

     {

         now->ls->turn=!now->ls->turn;

         swap(&now->ls->left,&now->ls->right);

     }

     if (!lr&&now->rs)

     {

         now->rs->turn=!now->rs->turn;

         swap(&now->rs->left,&now->rs->right);

     }

     swap(&now->ls,&now->rs);

     swap(&ret.l,&ret.r);

     if (ret.l)

     {

         ret.l->turn=!ret.l->turn;

         swap(&ret.l->left,&ret.l->right);

     }

     if (ret.r)

     {

         ret.r->turn=!ret.r->turn;

         swap(&ret.r->left,&ret.r->right);

     }

     return ret;

 }

 nodepair split(node* start)

 {

     pushdown(start);

     node* cen=start;

     nodepair ret(start->ls,start->rs);

     if (start->ls)

         start->ls->f=NULL;

     if (start->rs)

         start->rs->f=NULL;

     start->ls=start->rs=NULL;

     bool lr;

     if (start->f)

         if (start->f->ls == start)

             lr=false;

         else

             lr=true;

     node* now=start->f;

     start->f=NULL;

     while (now)

     {

         if (now->turn)

         {

             ret=pushdown(now,lr,ret);

             lr=!lr;

         }

         node* next=now->f;

         now->f=NULL;

         if (lr)

         {

             now->rs=ret.l;

             if (ret.l)

                 ret.l->f=now;

             update(now);

             ret.l=now;

         }

         else

         {

             now->ls=ret.r;

             if (ret.r)

                 ret.r->f=now;

             update(now);

             ret.r=now;

         }

         if (next)

         {

             if (next->ls==now)

                 lr=false;

             else

                 lr=true;

         }

         now=next;

     }

     ret.l=merge(ret.l,cen);

     return ret;

 }

 node* access(int num)

 {

     int now=num;

     node* lasttree=NULL;

     while (now!=)

     {

         nodepair km=split(&no[now]);

         if (lasttree)

             father[lasttree->left]=;

         lasttree = merge(km.l,lasttree);

         if (km.r)

             father[km.r->left]=now;

         now=father[lasttree->left];

     }

     return lasttree;

 }

 bool query(int x,int y)

 {

     int k1=access(x)->left;

     int k2=access(y)->left;

     return k1==k2;

 }

 void changeroot(int n)

 {

     node* road=access(n);

     road->turn=!road->turn;

     swap(&road->left,&road->right);

 }

 void Connect(int x,int y)

 {

     changeroot(y);

     access(x);

     father[y]=x;

 }

 void destroy(int x,int y)

 {

     changeroot(x);

     access(x);

     father[y]=;

 }

 int main()

 {

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

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

     int n;

     cin>>n;

     for (int i=;i<=n;++i)

     {

         no[i].num=i;

         father[i]=;

     }

     int q;

     char cmd[];

     scanf("%d",&q);

     for (int i=;i<=q;++i)

     {

         int j,k;

         scanf("%s%d%d",cmd,&j,&k);

         if (cmd[]=='C')

         {

             Connect(j,k);

         }

         if (cmd[]=='Q')

         {

             if (query(j,k))

                 printf("Yes\n");

             else

                 printf("No\n");

         }

         if (cmd[]=='D')

         {

             destroy(j,k);

         }

     }

     return ;

 }

2255ms 3769B

一坨翔啊！！！！不过麻麻再也不用担心我写不来动态树了。。。

准备过几天研究一下其他形式的可持久化TreapLCT，试着换种写法把常数降下来，代码量降下来。大概思想是先找到根，记录路径是走的左子树还是右子树，在走下来，感觉要好写很多。。。

现在觉得Splay和Treap各有各的优点，Treap好理解，一般较快。Splay特性很神奇，可以干一些奇奇怪怪的事情。。。

建议在我把常数降下来之前各位童鞋还是好好写Splay的LCT吧。。。

巴特西

脑洞大开加偏执人格——可持久化treap版的Link Cut Tree

最新文章

热门文章