BZOJ 2049 [Sdoi2008]Cave 洞穴勘测

题目大意

请你动态维护一棵树的连通性。

LCT维护。

LCT大概就是把一棵树分成好多好多的链，类似树链剖分，但是轻重链是动态的，每条链用一棵独立的Splay维护，之后就可以进行各种操作了。

很暴力，复杂度属于“能不用就不用，但是如果必须用就用”的玄学复杂度。

#include <cstdio>
#include <algorithm>
using namespace std;

#define N 10010

int n,m,ix,iy,c[2][N],fa[N];
char md[10];
bool rev[N];

inline int RI()
{
	int ret=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

inline void pushdown(int pos)
{
	if(rev[pos])
	{
		swap(c[0][c[0][pos]],c[1][c[0][pos]]);
		swap(c[0][c[1][pos]],c[1][c[1][pos]]);
		rev[c[0][pos]]^=1,rev[c[1][pos]]^=1;
		rev[pos]=0;
	}
}

void init(int pos)
{
	if(fa[pos]) init(fa[pos]);
	pushdown(pos);
}

inline bool isroot(int pos)
{
	return (c[0][fa[pos]]!=pos)&&(c[1][fa[pos]]!=pos);
}

inline void rotate(int tx)
{
	if(isroot(tx)) return;
	int ty=fa[tx],tz=fa[ty],tl=(c[1][ty]==tx),tr=tl^1;
	if(!isroot(ty)) c[c[1][tz]==ty][tz]=tx;
	fa[tx]=tz,fa[ty]=tx;
	fa[c[tr][tx]]=ty,c[tl][ty]=c[tr][tx],c[tr][tx]=ty;
}

inline void splay(int tx)
{
	init(tx);
	while(!isroot(tx))
	{
		int ty=fa[tx],tz=fa[ty];
		if(!isroot(ty))
		{
			if((c[0][ty]==tx)^(c[0][tz]==ty)) rotate(tx);
			else rotate(ty);
		}
		rotate(tx);
	}
}

inline void access(int pos)
{
	int tmp=0;
	while(pos)
	{
		splay(pos);
		c[1][pos]=tmp;
		tmp=pos,pos=fa[pos];
	}
}

inline void reverse(int pos)
{
	access(pos),splay(pos);
	swap(c[0][pos],c[1][pos]);
	rev[pos]^=1;
}

inline void link(int tx,int ty)
{
	reverse(tx),fa[tx]=ty;
}

inline void cut(int tx,int ty)
{
	reverse(tx),access(ty),splay(ty),c[0][ty]=fa[tx]=0;
}

inline int lookfor(int pos)
{
	access(pos),splay(pos);
	while(c[0][pos]) pos=c[0][pos];
	return pos;
}

int main()
{
	n=RI(),m=RI();
	while(m--)
	{
		scanf("%s",md);
		switch(md[0])
		{
			case 'C': ix=RI(),iy=RI(),link(ix,iy);break;
			case 'D': ix=RI(),iy=RI(),cut(ix,iy);break;
			case 'Q': ix=RI(),iy=RI(),printf("%s\n",(lookfor(ix)==lookfor(iy))?"Yes":"No");break;
		}
	}
	return 0;
}