一直没有点动态树这个科技树，因为听说只能用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吧。。。