【BZOJ2049】洞穴勘测 LCT算法学习

我好弱啊,到现在才写LCT板子。人家都把LCT归为基本算法了,然而我还是第一次写。没救了QAQ!!!

但是不管怎么样还是总结一下……

首先,题目大意很简单,维护一个森林,可以加边,删边,询问联通性。

用LCT直接维护就好

LCT的基本操作:

  • Access:把x到根的路径上的点合并为一个splay,具体操作就是,不断地splay(x),然后把x接到虚父亲的右儿子上。注意的是x的右儿子需要置为空。
  • splay:把x旋转到链所在splay的根,此时x的父亲是链的父亲。
  • MakeRoot:把x变成LCT的根,只需要Access(x),然后再打个翻转标记。
  • FindRoot:先Access(x),之后splay(x),从x开始向左找到的最左的节点就是x所在树的根。如果判断连通性,只需要找2个点的root是否相同。
  • 求LCA:对两个点分别Access(x),最后一次找到的虚父亲就是LCA。
  • Link:首先MakeRoot(x),接着把x的父亲设为y即可。
  • Cut:首先MakeRoot(x),接着Access(y),接着把x的右儿子和y的父亲设为空。

大概就是这么多,不管了我先贴代码……(缩行狂魔)

/*
  Program: 2049
  Copyright by G10 
  Please do not copy it
  Ryu jin no ken o kurae
*/
#include <bits/stdc++.h>
#define File(S) freopen(S".in","r",stdin);freopen(S".out","w",stdout);
#define RG register
#define IL inline
using namespace std;

typedef long long LL;
typedef unsigned UL;
typedef unsigned long long ULL;

IL LL getint()
{
    RG LL res=0,p=1;RG char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') p=-1,ch=getchar();
    while (ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*p;
}

const int INF=0x3f3f3f3f;
const int N=100050;

int n,m;
struct Node
{
    int fa,siz,s[2];bool rev;
    Node(){siz=1,s[0]=s[1]=fa=rev=0;}
}T[N];

IL void update(int x){if(!x)return;T[x].siz=T[T[x].s[0]].siz+T[T[x].s[1]].siz+1;}
IL void rever(int x){if(!x)return;T[x].rev^=1;swap(T[x].s[0],T[x].s[1]);}
IL void pushdown(int x){if (T[x].rev) rever(T[x].s[0]),rever(T[x].s[1]),T[x].rev=0;}
IL bool isRoot(int x){return T[T[x].fa].s[0]!=x&&T[T[x].fa].s[1]!=x;}
IL void ExPushDown(int x){if (!isRoot(x)) ExPushDown(T[x].fa);pushdown(x);}

IL void rotate(int x)
{
    RG int fa=T[x].fa,ga=T[fa].fa,f=T[fa].s[1]==x;
    if (!isRoot(fa)) T[ga].s[T[ga].s[1]==fa]=x;T[x].fa=ga;
    T[fa].s[f]=T[x].s[f^1];if (T[x].s[f^1]) T[T[x].s[f^1]].fa=fa;
    T[x].s[f^1]=fa,T[fa].fa=x;update(fa);update(x);   
}
#define CheckZZ(x) ((T[T[x].fa].s[1]==x)==(T[T[T[x].fa].fa].s[1]==T[x].fa))
IL void splay(int x){ExPushDown(x);while (!isRoot(x)) {if (!isRoot(T[x].fa)) rotate(CheckZZ(x)?T[x].fa:x);rotate(x);}}
IL void Access(int x){for (int y=0;x;y=x,x=T[x].fa) splay(x),T[x].s[1]=y;}
IL void MakeRoot(int x){Access(x),splay(x),rever(x);}
IL int FindRoot(int x){Access(x);splay(x);while(T[x].s[0])x=T[x].s[0];return x;}
IL void Link(int x,int y){MakeRoot(x),T[x].fa=y;}
IL void Cut(int x,int y){MakeRoot(x),Access(y),splay(y);T[y].s[0]=T[x].fa=0;}   

int main()
{
    //File("2049");
    n=getint();m=getint();char ch;int x,y;T[0].siz=0;
    while (m--) {
        do{ch=getchar();}while(ch<'A'||ch>'Z');x=getint(),y=getint();
        if (ch=='C') {Link(x,y);}if (ch=='D') {Cut(x,y);}
        if (ch=='Q') {printf((FindRoot(x)==FindRoot(y))?"Yes\n":"No\n");}
    }
    return 0;
}

 

不如来评论一发?