LCT面向对象鬼畜版
小菜鸟
2019-04-15 14:03:59
[点我去模板题](https://www.luogu.org/problemnew/show/P3690)
最近心血来潮，学习了传说中的Link-Cut Tree，在这里做一下总结
Link_Cut Tree是一种可以用于维护森林的数据结构，支持动态连边（link）、删边（cut）、对树上路径的信息进行查询和修改。
LCT基于实链剖分。什么是实链剖分？学过树剖你就应该可以理解了。
树剖通过对$size$最大的儿子连重边来将树转换为链进行处理。
实链剖分则采取一种神奇的方式进行处理：对每一个结点，都对其儿子中的零个或一个连一条实边，对其他儿子则不用管。同时，每个节点都记录了其父亲。简单地说，所有儿子都认父亲，但父亲只认实儿子（且实儿子要么不存在，要么只有一个）。
连续的实边构成的链，就将整个树（森林）划分开来。而边的虚实可以动态变化，从而使动态连边、删边得以实现。由于虚实动态变化较为复杂，因此要用更高级、更灵活的$Splay$代替线段树来对实链进行维护。
具体地，同一条实链上的结点置于同一棵$Splay$当中，在$LCT$中深度越小的结点，在$Splay$的中序遍历中越靠前。
每一棵$Splay$的根结点的父指针，指向这一条实链中深度最小的结点在$LCT$中的父亲，也称$Path father$。
蒟蒻深知没有图的痛苦……所以安利一下[FlashHu大佬的博客orz](https://www.cnblogs.com/flashhu/p/8324551.html)
写得真的很好，还有配图，我就是在那里学会的$LCT$。可惜代码是数组版，对我这等指针党死忠粉不是很友好QAQ
于是下定决心一定要把指针版代码封装好，完美地呈现出来。
~~于是就有了你们接下来看到的近300行代码emm~~
$OOP$的代码总是如此冗长难懂，所以下面一部分一部分讲述。（自带$Splay$讲解！）
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>//为了保证数据结构的健壮性，要用std::pair来应对非法状态
```
由于要借助$Splay$实现，所以写一个$Splay$类以方便之后对实链的维护。
```cpp
template<typename Value_type,typename Functor>//Value_type是要存的数据类型，Functor是要用到的运算的仿函数类型
//对Functor的要求：重载()运算符为满足结合律的二元运算，如+、*、gcd、min、max等，且参数与返回值类型均为Value_type
//类似STL中的算数算子和逻辑算子
//这一题是xor
//具体写法在主程序前
class LCT_splay:Functor
{
public:
struct Node;//存储单个结点的结构体
Node* __new_node(const Value_type&);//用于申请新结点的函数，改写该函数即可方便地改用内存池等
};
template<typename Value_type,typename Functor>
struct LCT_splay<Value_type,Functor>::Node
{
Value_type val,sum;//val保存结点中的值，sum保存以*this为根的子树的信息
Node* ftr;//父指针
Node* ch[2];//ch[0]左儿子，[1]右儿子
Node*& lc;//这才是我比较习惯的写法，只是为了rotate简单一点采取了折中方案
Node*& rc;//但在卡空间的题里面切忌用这种写法
//可以选择用宏定义
//#define lc ch[0]
//#define rc ch[1]
//然后再把构造函数里面的lc和rc注释掉就好了
bool rev;//在区间反转时的标记
Node(const Value_type& v): //构造函数
val(v),
sum(v),
ftr(NULL),
lc(ch[0]),
rc(ch[1]),
rev(0) {ch[0]=ch[1]=NULL;}//本来我写成ch{NULL,NULL}的形式，但这是C++11的语法，NOI系列比赛会爆掉
void reverse();//在当前结点上打反转标记
void push_down();//标记下传
void push_all();//在splay时将整条路径上的标记下传
void maintain();//维护子树信息
bool is_root();//判断当前结点是否为根。由于Splay中的根的父亲可能是Path father而非空结点，因此要特殊判断
void rotate();//单次旋转
void splay();//将当前结点伸展到根 //和普通splay不同，LCT中的Splay只需要旋转到根，因此没有目标结点参数
};
template<typename Value_type,typename Functor>
void LCT_splay<Value_type,Functor>::Node::reverse()
{
rev^=1;
}
template<typename Value_type,typename Functor>
void LCT_splay<Value_type,Functor>::Node::push_down()//和文艺平衡树写法一样
{
if(!rev)return;
rev=0;
Node* ptr=lc;
lc=rc;
rc=ptr;
if(lc!=NULL)lc->reverse();
if(rc!=NULL)rc->reverse();
}
template<typename Value_type,typename Functor>
void LCT_splay<Value_type,Functor>::Node::push_all()//为了使代码尽可能通用，本蒟蒻选择用系统栈而非手写栈来下传标记
{
if(!is_root())this->ftr->push_all();
push_down();
}
template<typename Value_type,typename Functor>
void LCT_splay<Value_type,Functor>::Node::maintain()
{
sum=val;
if(lc!=NULL)sum=Functor::operator()(lc->sum,sum);
if(rc!=NULL)sum=Functor::operator()(sum,rc->sum);
}
template<typename Value_type,typename Functor>
bool LCT_splay<Value_type,Functor>::Node::is_root()
{
return ftr==NULL||(ftr->lc!=this&&ftr->rc!=this);
//若父亲为空，则该结点必定为Splay的根
//否则，假如它不是其父亲的左右儿子（即是虚儿子），则该父亲为Path father，该节点为Splay的根
}
template<typename Value_type,typename Functor>
void LCT_splay<Value_type,Functor>::Node::rotate()
{
Node *nftr=ftr,*gftr=ftr->ftr;//nftr指向当前结点的原父亲，gftr指向祖父
bool is_rc=nftr->rc==this;//记录当前结点是哪个儿子
bool is_rf=gftr!=NULL&&gftr->rc==nftr;//记录当前结点的父亲是哪个儿子 //注意祖父可能为空，需要特判，我被这坑了一个小时
ftr=gftr;//重置当前结点的父亲
if(!nftr->is_root())gftr->ch[is_rf]=this;//若父亲不是根，则重置祖父的儿子
nftr->ch[is_rc]=this->ch[!is_rc];//将当前结点的一个儿子变成其原父亲对应的儿子
if(this->ch[!is_rc]!=NULL)this->ch[!is_rc]->ftr=nftr;//重置儿子的父指针
nftr->ftr=this;//将原父亲的父指针指向当前结点
this->ch[!is_rc]=nftr;//当前结点的对应儿子改为原父亲
nftr->maintain();//原父亲子树被改变，需要维护
maintain();//当前结点也需维护
/*旋转难以用语言表述，因而还是决定画图
若当前结点x为左儿子
f x
/ \ / \
x b rotate(x) l f
/ \ ------------> / \
l r r b
x为右儿子，同理
f x
/ \ / \
b x rotate(x) f r
/ \ ------------> / \
l r b l
*/
}
template<typename Value_type,typename Functor>
void LCT_splay<Value_type,Functor>::Node::splay()
{
push_all();//先下传旋转路径上所有标记
while(!is_root())//注意这里和普通Splay有所区别
{
Node *nftr=ftr,*gftr=ftr->ftr;
if(nftr->is_root())rotate();//判断一次单旋就到根的情况
else
{
if((gftr->lc==nftr)^(nftr->lc==this))rotate();//双旋是个好习惯
else nftr->rotate();//若当前结点与父节点同为左儿子或右儿子，先上旋父节点，再上旋当前结点
//否则连续两次上旋当前结点
rotate();
//这种双旋方式来自于传说中的AVL树，使复杂度有了一定的保证
}
}
}
template<typename Value_type,typename Functor>
typename
LCT_splay<Value_type,Functor>::Node* LCT_splay<Value_type,Functor>::__new_node(const Value_type& v)//申请新结点的函数
{
return new Node(v);
}
```
Splay部分完
接下来是LCT类
```cpp
template<typename Value_type,typename Functor>
class link_cut_tree:public LCT_splay<Value_type,Functor>//显然LCT的结构完全依赖于Splay，所以直接继承就可以了
{
typedef typename LCT_splay<Value_type,Functor>::Node Node;//不写这一句的话后面的代码会很难看
private:
void access(Node*);//将结点与它所在的LCT子树的根之间的实链打通
void make_root(Node*);//将结点置为它所在的LCT子树的根
Node* find_root(Node*);//找到结点所在LCT子树的根
bool split(Node*,Node*);//在两个结点之间打通一条实链
public:
struct iterator;//迭代器，只是为了保证封装性并提升逼格，实际用处不大
iterator make_node(const Value_type&);//新建结点
//不用担心用函数新建结点会拖慢速度，除了虚函数和递归函数以外的成员函数是内联的
bool link(const iterator&,const iterator&);//在两个结点间连一条边
bool cut(const iterator&,const iterator&);//切断两结点之间的边
std::pair<bool,Value_type> query(iterator,iterator);//查询两结点之间路径上的信息
bool modify(const iterator&,const Value_type&);//单点修改 //区间修改也不难写，但我比较懒
};
template<typename Value_type,typename Functor>
struct link_cut_tree<Value_type,Functor>::iterator
{
private:
Node* ptr;
friend class link_cut_tree;//对LCT类公开，方便LCT类进行操作
//否则会很难处理
public:
Value_type operator*()const{return ptr->val;}//使迭代器有类似指针的用法
iterator(Node* p=NULL):ptr(p) {}
iterator(const iterator& iter):ptr(iter.ptr) {}
};
template<typename Value_type,typename Functor>
void link_cut_tree<Value_type,Functor>::access(Node* ptr)
{
for(Node* nptr=NULL;ptr!=NULL;nptr=ptr,ptr=ptr->ftr)//从当前结点一直向上迭代至所在的LCT子树的根
{
ptr->splay();//先将当前结点伸展
//由于结点在Splay中的右儿子在LCT中的深度大于当前结点
//所以在伸展当前结点后，其在Splay中的右儿子即是其实儿子
ptr->rc=nptr;//那么直接将其实儿子修改为当前已经拉出的实链
ptr->maintain();//当前结点子树发生变化，需要维护子树信息
}
}
template<typename Value_type,typename Functor>
void link_cut_tree<Value_type,Functor>::make_root(Node* ptr)//这个函数需要一点感性理解
{
access(ptr);//先打通当前结点与根的实链
//由于根从该实链的一端到了另外一端，整根实链的深度发生了反转
//因此要用Splay的区间反转功能
ptr->splay();//参见文艺平衡树
ptr->reverse();
//至于其他的实链，你可以想像它们都是指向该实链的
//即该实链是其他实链的“父链”
//所以其他实链内结点相对深度不会发生变化
}
template<typename Value_type,typename Functor>
typename
link_cut_tree<Value_type,Functor>::Node* link_cut_tree<Value_type,Functor>::find_root(Node* ptr)
{
access(ptr);//打通实链后，根即是整棵Splay中最左侧的结点
ptr->splay();//因此伸展当前结点
while(ptr->lc!=NULL)ptr->push_down(),ptr=ptr->lc;//从Splay的根开始，一路向左搜索就可以找到LCT的根
ptr->splay();//相当于前置移动算法，保证复杂度
return ptr;
}
template<typename Value_type,typename Functor>
bool link_cut_tree<Value_type,Functor>::split(Node* sptr,Node* eptr)//拉出sptr至eptr的实链
{
make_root(sptr);//很简单
if(find_root(eptr)!=sptr)return 0;//把sptr变成LCT的根以后直接打通eptr至sptr的实链即可
//但为了避免不合法的情况，判一下连通性
//find_root自带access，所以不用再写
eptr->splay();//最后将eptr伸展，这样访问eptr即可取得整条实链的信息
return 1;
}
template<typename Value_type,typename Functor>
typename
link_cut_tree<Value_type,Functor>::iterator link_cut_tree<Value_type,Functor>::make_node(const Value_type& v)
{
return iterator(LCT_splay<Value_type,Functor>::__new_node(v));//调用Splay的申请函数并包装为迭代器
}
template<typename Value_type,typename Functor>
bool link_cut_tree<Value_type,Functor>::link(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
make_root(sptr);//先将sptr置为根
if(find_root(eptr)==sptr)return 0;//判连通性，若连通则连边失败
sptr->ftr=eptr;//直接将eptr变为sptr的虚儿子
return 1;
}
template<typename Value_type,typename Functor>
bool link_cut_tree<Value_type,Functor>::cut(const iterator& siter,const iterator& eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
make_root(sptr);//先将eptr置为根
if(find_root(eptr)!=sptr||eptr->ftr!=sptr||eptr->lc!=NULL)return 0;
//判断两点是否连通
//注意find_root以后，两点间实链被打通，即两点在同一Splay中
//而sptr在find_root的最后一步被上旋至根
//所以两点若相接，则eptr的父亲必须为sptr
//同时eptr左子树必须为空
//只有这样才保证在Splay的中序遍历中，两点是相接的
//也即两点间有边
eptr->ftr=NULL;//断开eptr与sptr间的虚边
sptr->lc=NULL;//断开实边
sptr->maintain();//子树发生了改变，需要维护
return 1;
}
template<typename Value_type,typename Functor>
std::pair<bool,Value_type> link_cut_tree<Value_type,Functor>::query(iterator siter,iterator eiter)
{
Node* sptr=siter.ptr;
Node* eptr=eiter.ptr;
if(!split(sptr,eptr))return std::make_pair(0,Value_type());//若两点不连通，则pair中bool值为FALSE
return std::make_pair(1,eptr->sum);//否则，由于split最后将eptr伸展，直接访问eptr即可
}
template<typename Value_type,typename Functor>
bool link_cut_tree<Value_type,Functor>::modify(const iterator& iter,const Value_type& v)
{
Node* ptr=iter.ptr;
if(ptr==NULL)return 0;
ptr->splay();//为了避免对其他结点的子树信息造成破坏，先将要修改的结点伸展到根
ptr->val=v;
ptr->maintain();//自身发生改变，需要维护
return 1;
}
```
以上就是LCT的核心内容，应该说注释非常详细了（实际上写好注释感觉像重新学了一遍LCT，自己都有了不少新的理解）
打完封装的板子，终于苦尽甘来，我们迎来了最后的步骤！
```cpp
template<typename Argument_type,typename Result_type>
class Xor//定义Xor类，该类的实例即是计算x^y的仿函数
//注意观察格式，这种写法很重要
//在STL中有重要的应用
{
public:
Result_type operator()(const Argument_type& x,const Argument_type& y)const
{
return x^y;
}
};
//快读快写加速还是很大的
template<typename T>
void read(T& x)
{
bool f=0;
x=0;
char c=std::getchar();
while(c<'0'||c>'9')f|=(c=='-'),c=std::getchar();
while(c>='0'&&c<='9')x=x*10+(c^48),c=std::getchar();
}
template<typename T>
void write(T x)
{
if(x<0)std::putchar('-'),x=-x;
if(x>=10)write(x/10);
putchar((x%10)^48);
}
link_cut_tree<int,Xor<int,int> > my_LCT;
link_cut_tree<int,Xor<int,int> >::iterator iters[300005];
int main()
{
int n,m,x,y,op;
read(n);
read(m);
for(int i=1;i<=n;++i)read(x),iters[i]=my_LCT.make_node(x);
for(int i=0;i<m;++i)
{
read(op);
read(x);
read(y);
switch(op)
{
case(0):
write(my_LCT.query(iters[x],iters[y]).second);
putchar('\n');
break;
case(1):
my_LCT.link(iters[x],iters[y]);
break;
case(2):
my_LCT.cut(iters[x],iters[y]);
break;
case(3):
my_LCT.modify(iters[x],y);
break;
}
}
}
```
后记：$LCT$能方便地解决很多动态树的问题，是一种强大的数据结构。博主之所以写下如此详细的注释，一来是为了方便看这篇博文的大佬们理解，二来也是为了加深自己的理解，强化自己的记忆。另外，OOP虽然使代码变得冗长，但也大幅增强了代码的通用性。多写写OOP代码，有助于提升思维和手速。以后进行工程开发时，OOP更是不可或缺。
最后，蒟蒻LDL祝大家新的一年代码越写越好，越写越快，越写越顺溜，早日AK\*OI(\*是通配符)。新年快乐！
（本文于2019.02.04发布于CSDN博客，04.15重放在此）