传送门

解题思路

  \(lct\)就是基于实链剖分,用\(splay\)来维护每一条实链,\(lct\)的维护对象是一棵森林。\(lct\)支持很多神奇的操作:

\(1、\) \(access\):这是\(lct\)的核心操作,就是将一个点与根打通,就是把路径上的所有边变成实边,具体就是转到根,换儿子,更新信息。

\(2、\)\(makeroot\):将指定点作为原树的根,就是先\(access\)后,\(x\)一定是深度最大的点,再\(splay\) \(x\) 后将\(x\)的儿子进行翻转,这样就可以使\(x\)变为深度最小的节点,即为根。

\(3、\)\(findroot\) :判断两点是否联通,就是先\(access\)后,\(splay\) \(x\),然后这样的话\(x\)就一定只有左儿子,因为\(x\)是深度最深的点,然后一直跳左儿子即可。

\(4、\)\(split\) :访问\(x\)到\(y\)这条链,就是先\(makeroot\) \(x\),让\(x\)变为根,再\(access\) \(y\)把\(y\)与\(x\)打通,最后把\(y\)转上去就行了。

\(5、\)\(link\):连边,就是把其中一个点\(makeroot\),然后直接连一条虚边。

\(6、\) \(cut\):断边,先把\(x\)与\(y\)的路径拿出来,就是\(split\)操作,然后要判断一下\(y\)的左儿子是否为\(x\),还要判断一下\(x\)是否有右儿子。

剩下的一些操作跟\(splay\)比较像。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib> using namespace std;
const int MAXN = 300005; inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
} int n,m,w[MAXN];
int fa[MAXN],sum[MAXN],ch[MAXN][2];
bool tag[MAXN]; inline bool check(int x){
return (x==ch[fa[x]][1]);
} inline bool isroot(int x){
return (ch[fa[x]][0]!=x && ch[fa[x]][1]!=x);
} inline void pushup(int x){
sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^w[x];
} inline void pushdown(int x){
if(tag[x]){
if(ch[x][0]) tag[ch[x][0]]^=1,swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
if(ch[x][1]) tag[ch[x][1]]^=1,swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
tag[x]=0;
}
} inline void update(int x){
if(!isroot(x)) update(fa[x]);pushdown(x);
} inline void rotate(int x){
int y=fa[x],z=fa[y];bool chk=check(x);
if(!isroot(y)) ch[z][(y==ch[z][1])]=x;
ch[y][chk]=ch[x][chk^1];fa[ch[x][chk^1]]=y;
fa[y]=x;fa[x]=z;ch[x][chk^1]=y;
pushup(y);pushup(x);
} inline void splay(int x){
update(x);
for(;!isroot(x);rotate(x))
if(!isroot(fa[x])) rotate(check(x)==check(fa[x])?fa[x]:x);
} inline void access(int x){
for(int y=0;x;y=x,x=fa[x])
splay(x),ch[x][1]=y,pushup(x);
} inline void makeroot(int x){
access(x);splay(x);
tag[x]^=1;swap(ch[x][0],ch[x][1]);
} inline int findroot(int x){
access(x);splay(x);
while(ch[x][0]) pushdown(x),x=ch[x][0];
return x;
} inline void split(int x,int y){
makeroot(x);access(y);splay(y);
} inline void link(int x,int y){
if(findroot(x)==findroot(y)) return;
makeroot(x);fa[x]=y;
} inline void cut(int x,int y){
if(findroot(x)!=findroot(y)) return;
split(x,y);if(ch[y][0]==x && !ch[x][1]) fa[x]=0,ch[y][0]=0,pushup(y);
} int main(){
n=rd(),m=rd();int op,x,y;
for(int i=1;i<=n;i++) w[i]=rd();
while(m--){
op=rd(),x=rd(),y=rd();
if(op==0) {split(x,y);printf("%d\n",sum[y]);}
if(op==1) link(x,y);
if(op==2) cut(x,y);
if(op==3) splay(x),w[x]=y;
}
return 0;
}
05-23 10:10