http://www.zybbs.org/JudgeOnline/problem.php?id=2002

终于写出LCT了……以前一直觉得LCT好难，现在发现原因是那时候我还没怎么用过splay。用SplayA掉一些题目以后再来看LCT，发现LCT实在是太简单了！从开始写（splay拷了自己的模板）到提交1A，总共才10+分钟！

然后开始无爱的刷Rank……不过失败了……ym7k+的122次提交……我不会告诉别人你是用O3的代码反汇编出来再交asm的 =。=

其实LCT的核心就是Access操作，即打通一个点到根的路径（且这条路径不能向下延伸），然后就可以处理这个点到某个祖先的路径上的询问了。具体操作就是实边和虚边的互相转化，杨哲等人的论文还是讲得很清楚的……这里不讲了。

如果是i,j两点间路径，那么需要求LCA。这时可以让access返回最后一次link操作时的父亲，那么access(i)后access(j)返回的就是LCA的指针了。

如果你不会Splay，那你最多只能大致了解LCT。如果你觉得你会Splay但是还没有A过题，那你想写LCT是非常困难的。想熟练快速并且悠闲地打出一个LCT模板，那么至少用SplayA掉2种（普通平衡树/代替线段树），每种2道不同类型的题目。

一般的LCT甚至不用Rank/Find等操作。比如这题只需要splay和Access两个操作即可！几乎不用花什么脑筋！

顺便牢骚一句，除了IO优化以外的任何刷RANK手段都是无耻的！！！

#include <stdio.h>
#define maxn 200000
typedef struct _Splay{struct _Splay *c[2],*f,*p;int s;}Splay,*PSplay;
Splay null,st[maxn];
char str[1500000],*p=str,out[400000],*o=out;
inline PSplay updt(PSplay x){if(x!=&null)x->s=x->c[0]->s+x->c[1]->s+1;return x;}
inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}
inline PSplay node(PSplay x,PSplay p){x->f=x->c[0]=x->c[1]=&null;x->s=1;x->p=p;return x;}
inline PSplay rot(PSplay x){
	PSplay fx=x->f,ffx=fx->f;
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if((x->f=ffx)!=&null)ffx->c[fc]=x;
		updt((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return updt(x);
}inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}inline PSplay Access(PSplay x){
	PSplay t=splay(x,&null);x->c[1]=x->c[1]->f=&null;
	while((x=splay(extr(x,0),&null))->p!=&null){
		splay(x->p,&null)->c[1]->f=&null;
		x=(x->p->c[1]=x)->f=x->p;
	}return t;
}inline void print(x){
	char buf[10],*b=buf;
	while(x)*b++=x%10+48,x/=10;
	while(b--!=buf)*o++=*b;
	*o++='\n';
}main(){
	int n,i=-1,x,k,t;fread(p,1,1500000,stdin);
	null.f=null.c[0]=null.c[1]=&null;
	for(n=getint();++i!=n;node(st+i,i+(k=getint())>=n?&null:st+i+k));
	for(t=getint();t--;)if(getint()==1)print(splay(Access(st+getint()),&null)->c[0]->s+1);
	else{
		splay(st+(x=getint()),&null)->c[0]->f=&null;
		st[x].c[0]=&null;
		updt(updt(st+x)->p=x+(k=getint())>=n?&null:st+x+k);
	}*--o=0;return puts(out),0;
}

下面是些无关的话题：

1.我真心写不出LCT的模板啊……谁来告诉我除了Access还有啥操作？

2.今天数学课上突然弄懂了DC3（Skew）算法……太他妈神奇了，什么时候一定要去试试！

3.我觉得代码短看起来爽啊……我一开始不会LCT很可能和某些80行以上的超长代码有关……我会想，LCT这么长，我肯定学不会……

上面那个其实不是标准的LCT……又写了标准的……就是每个点只记录一个父亲的，然后一条链的splay中的根的父亲是这条链的最上面那个点的真实父亲。

这样弄了以后发现有点晕……两题调了我6小时，然后这题发现是有一句代码的执行顺序在本地和OJ上不同导致TLE……洞穴勘测那题发现是少了个pushdown……欲哭无泪啊……

洞穴勘测那题是好题，就是数据太委了，暴力就能过……

#include <stdio.h>
#define maxn 200000
typedef struct _Splay{struct _Splay *c[2],*f;int s;}Splay,*PSplay;
Splay null,st[maxn];
char str[1500000],*p=str,*o=str;
inline PSplay fa(PSplay x){return x->f->c[0]==x||x->f->c[1]==x?x->f:&null;}
inline PSplay updt(PSplay x){x->s=x->c[0]->s+x->c[1]->s+1;return x;}
inline PSplay node(PSplay x,PSplay f){x->f=f;x->c[0]=x->c[1]=&null;x->s=1;return x;}
inline PSplay rot(PSplay x){
	PSplay fx=fa(x),ffx=fa(fx);
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		x->f=fx->f;
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if(ffx!=&null)ffx->c[fc]=x;
		updt((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	PSplay fx,ffx;if(x==&null)return x;
	for(;(fx=fa(x))!=p;rot(x))if((ffx=fa(fx))!=p)rot((ffx->c[1]==fx)==(fx->c[1]==x)?fx:x);
	return updt(x);
}inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}inline PSplay Access(PSplay x){
	PSplay t=&null,y=x;
	while(splay(x,&null)->c[1]=t,x->f!=&null)x=(t=updt(x))->f;
	return splay(y,&null);
}inline void print(x){
	char buf[10],*b=buf;
	while(x)*b++=x%10+48,x/=10;
	while(b--!=buf)*o++=*b;
	*o++='\n';
}main(){
	int n,i=-1,x,k,t;fread(p,1,1500000,stdin);
	null.f=null.c[0]=null.c[1]=&null;
	for(n=getint();++i!=n;node(st+i,i+(k=getint())>=n?&null:st+i+k));
	for(t=getint();t--;)if(*++p==49)p++,print(Access(st+(x=getint()))->c[0]->s+1);
	else if(*p==50){
		p++;Access(st+(x=getint()))->c[0]->f=&null;st[x].c[0]=&null;
		updt(st+x)->f=x+(k=getint())>=n?&null:st+x+k;
	}else t++;*--o=0;return puts(str),0;
}

• inline
• block