首页 > 其他分享 >Splay,LCT,ETT

Splay,LCT,ETT

时间:2023-08-20 22:57:42浏览次数:41  
标签:fp splay LCT ETT int tr Iv Splay fa

Splay 核心代码。

总结就是双旋

void rot(int x,int &k){
	int y=tr[x].fa,z=tr[y].fa;
	int kd=(tr[y].son[0]==x)?0:1;
	if(y==k) k=x;
	else {
		if(tr[z].son[0]==y) tr[z].son[0]=x;
		else tr[z].son[1]=x;
	}
	tr[y].son[kd]=tr[x].son[!kd]; tr[tr[y].son[kd]].fa=y;
	tr[x].son[kd^1]=y; tr[y].fa=x; tr[x].fa=z;
	pushup(y); pushup(x);
}
void splay(int x,int &k){
	while(x!=k){
		int y=tr[x].fa,z=tr[y].fa;
		if(y!=k){
			if((tr[y].son[0]==x) ^ (tr[z].son[0]==y)) rot(x,k);
			else rot(y,k);
		}
		rot(x,k);
	}
}

LCT

\(\rm FlashHu\) 爷的博客

对于一棵树中,每个节点选中一个儿子的边为实边,其他为虚边,这样就构成了若干个实链,每个 \(Splay\) 维护一条实链。基于这样的实链剖分, \(LCT\) 应运而生。 \(LCT\) 维护的对象其实是一个森林。

支持的操作如下:

  • 查询、修改链上的信息(最值,总和等)
  • 换根
  • 动态连边、删边
  • 动态维护连通性
  • 查询、修改子树信息(?)

\(LCT\) 的主要性质:

  • 每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径,且中序遍历Splay得到的每个点的深度序列严格递增。
  • 每个节点包含且仅包含在一个 \(\rm Splay\) 中。
  • 边分为实边贺虚边,实边包含在 \(Splay\) 中,虚边由一棵 \(\rm Splay\) 指向另外一个节点(该 \(\rm Splay\) 中中序遍历最靠前的点在原树中的父亲)。

\(\rm Access(x)\)

定义打通该节点到根节点的实链。构造出一个 \(\rm Splay\) 表示根到指定点的实链 。

将指定点 \(\rm Splay\) 到根节点。直接将虚边变成实边。

若原来的虚边指向父亲为 \(fp\) ,则直接根据中序遍历,将 \(fp\) 的右儿子指向 \(x\) 。然后继续向上重复操作,一直到根节点。

Iv access(int x){
	for(int y=0;x;y=x,x=tr[x].fa)
		splay(x) , tr[x].c[1]=y, pushup(x);
}

\(\rm evert\)

换根。 打通指定点到根的实链然后原本是中序遍历最后一个节点,变成第一个节点,交换左右儿子即可。

需要下传交换标记,后文会提到。

Iv revr(int u){ swap(tr[x].c[0],tr[x].c[1]); tr[x].rev^=1;}
Iv pushdn(int p) {
	if(tr[p].rev){
		if(tr[p].c[0]) revr[tr[p].c[0]];
		if(tr[p].c[1]) revr[tr[p].c[1]];
		tr[p].rev=0;
	}
}
inline void evert(int x){
	access(x); splay(x); revr(x);
}

\(\rm splay\)

因为有了下传标记的操作,所以 \(\rm splay\) 部分有所更改。
注意标记要从上到下下传。

Iv pdnw(int p){
	if(!isroot(p)) pdnw(tr[p].fa);
	pushdn(p);
}
Iv rotate(int p){
	int fp=tr[p].fa,gp=tr[fp].fa;
	int d=gd(p);
	if(isroot(fp)) tr[p].fa=tr[fp].fa;
	else cnet(gp,gd(fp),p);
	cnet(fp,d,tr[p].c[!d]); cnet(p,!d,fp);
	pushup(fp); pushup(p);
}
Iv splay(int p){
	pdnw(p);
	while(!isroot(p)){
		int fp=tr[p].fa;
		if(!isroot(fp)){
			if(gd(fp)==gd(p)) rot(fp);
			else rot(p);
		}
		rot(p);
	}
}

\(\rm findrt\)

找到根节点。 先将 \(x\) \(\rm splay\) 到根,根据中序遍历和二叉搜索树的性质查找。

记得 \(\rm pushdown\)。

inline int findrt(int u){
	access(u); splay(u); pushdn(u);
	while(tr[u].c[0]) u=tr[u].c[0],pushdn(u);
	splay(u);
	return u;
}

#### $\rm link$
连接一条边。
```cpp
Iv link(int u,int v){
	evert(u); if(findrt(v)!=u)	tr[u].fa=v;
}
*/

\(\rm cut\)

断开一条边。

Iv cut(int u,int v){
	evert(v); access(u); splay(u);
	if(tr[v].c[1] || tr[u].c[0]!=v) return ;
	cutd(u,0); pushup(u);
}

\(\rm splitl\)

将 \(u\to v\) 这条链放到一个 \(\rm Splay\) 里面,且让 \(u\) 的中序遍历比 \(v\) 小。

并将 \(v\) \(\rm splay\) 使得 \(v\) 的左儿子为 \(u\)。

不过我还是喜欢将这个函数拆出来写(。 可以用来查询信息???

Iv splitl(int u,int v){
	evert(u); access(v); splay(v);
}

完整代码:

namespace LCT{
#define ls tr[p].c[0]
#define rs tr[p].c[1]
struct node{
	int c[2],fa;
	int rev;
	node(){c[0]=c[1]=fa=0;rev=0;}
} tr[N+5]; 
inline bool gd(int p) { return tr[tr[p].fa].c[1]==p;}
inline bool isroot(int p) { return !tr[p].fa || tr[tr[p].fa].c[gd(p)]!=p;}
Iv cnet(int u,int d,int v){if(u) tr[u].c[d]=v; if(v) tr[v].fa=u;}
Iv cutd(int u,int d){ tr[ tr[u].c[d] ].fa=0 ; tr[u].c[d]=0;}
Iv revr(int u){ swap(tr[u].c[0],tr[u].c[1]); tr[u].rev^=1;}
Iv pushdn(int p) {
	if(tr[p].rev){
		if(tr[p].c[0]) revr(tr[p].c[0]);
		if(tr[p].c[1]) revr(tr[p].c[1]);
		tr[p].rev=0;
	}
   //以及其他需要维护的信息
}
Iv pushup(int p) { ;}
Iv pdnw(int p){
	if(!isroot(p)) pdnw(tr[p].fa);
	pushdn(p);
}
Iv rot(int p){
	int fp=tr[p].fa,gp=tr[fp].fa;
	int d=gd(p);
	if(isroot(fp)) tr[p].fa=tr[fp].fa;
	else cnet(gp,gd(fp),p);
	cnet(fp,d,tr[p].c[!d]); cnet(p,!d,fp);
	pushup(fp); pushup(p);
}
Iv splay(int p){
	pdnw(p);
	while(!isroot(p)){
		int fp=tr[p].fa;
		if(!isroot(fp)){
			if(gd(fp)==gd(p)) rot(fp);
			else rot(p);
		}
		rot(p);
	}
}
Iv access(int x){
	for(int y=0;x;x=tr[y=x].fa)
		splay(x) , tr[x].c[1]=y, pushup(x);
}
Iv evert(int x){
	access(x); splay(x); revr(x);
}
inline int findrt(int u){
	access(u); splay(u); 
	while(tr[u].c[0]) pushdn(u),u=tr[u].c[0];
	splay(u);
	return u;
}
Iv splitl(int u,int v){
	evert(u); access(v); splay(v);
}
Iv link(int u,int v){
	evert(u); if(findrt(v)==u) return ;
   splay(v); tr[u].fa=v;
}
Iv cut(int u,int v){
	evert(v); access(u); splay(u);
	if(tr[v].c[1] || tr[u].c[0]!=v) return ;
	cutd(u,0); pushup(u);
}
#undef ls
#undef rs
}
using namespace LCT;

一些 LCT 的套路。

  • 有些题可以把操作从后往前做,就可以把题目中的删边转化成加边。

  • 边权转点权。 如有边 \(u\stackrel{E_i}{\longrightarrow}v\),点 \(u\) 和 点 \(v\) 由边 \(E_i\) 相连。 我们可以开一个新的点 \(x\) 表示边 \(E_i\) 。将边权信息存到点权上。 连接 \(u-x,v-x\)。维护生成树。

  • 维护子树信息 ,分为实子树和虚子树的贡献。实子树好维护,虚子树需要在改变虚实边时处理,即 \(\rm link\) 和 \(\rm assert\) 的时候特殊处理。

  • 最小深度,树的直径,先鸽了。

应用:

维护生成树

[WC2006]水管局长

删边转加边,维护最小生成树。

最小差值生成树

将边从大到小加边,然后动态维护最小生成树。本质是枚举边的最小值,通过维护最小生成树使得最大值最大。

维护联通性&双联通分量

P2147 [SDOI2008] 洞穴勘测

并查集只能撤销不能删除。用 LCT 完成删边加边操作,findrt 查询连通性。

P2542 [AHOI2005] 航线规划

首先离线,删边转加边。要求关键路径,本质是要求我们把边双缩成一点后再查询两点距离。可以利用 LCT 来维护这个操作

每次把一条链变成一个环时,可以直接暴力地把这个链拆开,用并查集把链上每一个点连到新的代表这个环的点。就做完了。注意 \(access\) 找父亲时要查找并查集的父亲

int geph(int x){
	if(Fa[x]==x) return x;
	else return Fa[x]=geph(Fa[x]);
}
Iv access(int x){
	for(int y=0;x;y=x,x=tr[y].fa=geph(tr[y].fa))
		splay(x) , tr[x].c[1]=y, pushup(x);
}
void del(int p,int fu){
	Fa[p]=fu;
	if(tr[p].c[0]) del(tr[p].c[0],fu);
	if(tr[p].c[1]) del(tr[p].c[1],fu);
}
Iv link(int u,int v){
	if(u==v) return ;
	evert(u); if(findrt(v)!=u) {tr[u].fa=v; return ;}
	del(tr[u].c[1],u); tr[u].c[1]=0; pushup(u);
}

维护树上深度&直径

[USACO18FEB]New Barns P

做法一:动态维护树的深度。理论上也支持删边操作,复杂度 \(O(n\log^2 n)\)。

对于查询,我们将查询点 \(\rm makeroot\) 只要能查询这个点的最大深度即可。

我们用一个 \(multiset\) 将轻节点的信息存起来。因为 splay时所代表的链传递上去的信息不变,所以在 \(access\) 的时候修改即可。

我们记录两个值 \(mxd,mxz\) 。记录的是 \(splay\) 表示的链中,这个节点的子树(不包含链中深度比他小的节点)的最大深度,因为翻转的时候树的深度会颠反,所以同时记录反转后的深度交换即可。
根据左右子树顺序传递信息。

tr[p].mxd=max(tr[ls].mxd,max(*(--tr[p].sdp.end()),tr[rs].mxd)+tr[ls].siz+1);
tr[p].mxz=max(tr[rs].mxz,max(*(--tr[p].sdp.end()),tr[ls].mxz)+1+tr[rs].siz);

record

做法二:动态维护树的直径。

关于直径的性质:

  • 两棵树合并后,新的直径的两个端点一定来源于原来两条直径中的四个端点。
  • 一个点距离最远的点一定是直径两个端点之一。

那么我们将直径信息存在并查集的根节点,合并时利用 \(\rm LCT\) 求距离来算出新的直径。 复杂度 \(O(n\log n)\)

查询子树信息

[BJOI2014] 大融合

查询本质是求两颗子树大小的乘积。维护子树的大小,查询的时候直接单独拉出来这条边即可。

将实子树大小和虚子树大小分开处理。 虚子树大小在 \(assert\) 的时候维护一下。

看代码理解吧。

Iv pushup(int p) { tr[p].sz=tr[lc].sz+tr[rc].sz+tr[p].szx+1; }
Iv access(int x){
	for(int y=0;x;x=tr[y=x].fa){
		splay(x); tr[x].szx+=tr[tr[x].c[1]].sz-tr[y].sz;
		tr[x].c[1]=y; pushup(x);
	}
}
Iv link(int u,int v){
	evert(u);  evert(v);
	tr[u].fa=v;tr[v].szx+=tr[u].sz; pushup(v);
}

服了,调了一天,维护信息跟虚边有关的一定要将 \(u\) 和 \(v\) 都转到跟,否则,信息会无法更新 。

P4299 首都

不难发现,题目求的就是各个树的重心。

重心性质:

  • 把两棵树通过一条边相连,新的树的重心在原来两棵树重心的连线上。
  • 当树的大小为奇数是,重心是唯一的,否则,重心有两个且由一条边连接。
  • 重心的所有子树大小均不大于树的大小 \(S/2\)。互为充要条件,可以证明。

根据这些性质,我们将重心存到并查集的根,每次合并两棵树,把两个重心的路径拿出来,寻找新的重心,在 Splay 树上二分。

具体的,如果一个点不为重心,那么重心只会存在于左儿子和右儿子的一个方向。根据重心性质,我们递归儿子重量更大的一边。根据重心性质可以证明。 复杂度 \(O(n\log n)\)。

inline int findzx(int p){
	int lsm=0,rsm=0,S=tr[p].sz,np=N+5;
	while(p){
		pushdn(p);
		int lm=tr[ls].sz+lsm,rm=tr[rs].sz+rsm;
		if(lsm>S/2 || rsm>S/2) break;
		if(lm<=S/2 && rm<=S/2){
			if(S & 1) { np=p; break;}
			else {
				if(np>p) np=p;
				else break;	
			}
		}
		if(lm<rm)  lsm+=tr[ls].sz+tr[p].szx+1 , p=rs;
		else rsm+=tr[rs].sz+tr[p].szx+1, p=ls;
	}
	splay(np);
	return np;
}

还有一种更为朴素的做法,启发式合并。重心性质

添加或者删除一个点,重心只一个一次,因此,暴力地加点判断重心大概可以做,可能会比较复杂。 \(O(n\log^2n)\)。

P5212 SubString

SAM + LCT 合成品。动态维护后缀链接,查询子树大小。

好题:

P4332 [SHOI2014] 三叉神经树

P3703 [SDOI2017] 树点涂色

标签:fp,splay,LCT,ETT,int,tr,Iv,Splay,fa
From: https://www.cnblogs.com/shui-dream/p/17644796.html

相关文章

  • P5 UVA1308 Viva Confetti
    这道题主要是去理解所谓的"看得见"的面积是怎么组成的。对于每个露出来的面积,其实是由多个圆弧所组成的。是的,这就是为什么要以圆弧为引入点来解决此题的原因。那该怎么找露出来的面积呢?题目有说,在一定范围内不影响答案,所以考虑找每个圆弧的中点,然后平移一点点距离,再从覆盖顺......
  • kettle学习
    安装网络上提供的很第三方下载链接失效了,最后找了半天直接去官网下载了。PentahoCommunityEdition.社区版是免费的。点击DownloadNow进行下载。下面的下载目录很多,结合其他教程,下载其中名为pdi-ce-9.4.0.0-343.zip的下载项,当然版本号可能因为更新略有不同。下载过程可能比较......
  • Netty编解码&粘包拆包&心跳机制&断线自动重连
    Netty编解码Netty涉及到编解码的组件有Channel、ChannelHandler、ChannelPipe等,先大概了解下这几个组件的作用。ChannelHandlerChannelHandler充当了处理入站和出站数据的应用程序逻辑容器。例如,实现ChannelInboundHandler接口(或ChannelInboundHandlerAdapter),你就可以接收入站事件......
  • Netty核心功能与线程模型
    Netty初探NIO的类库和API繁杂,使用麻烦:需要熟练掌握Selector、ServerSocketChannel、SocketChannel、ByteBuffer等。开发工作量和难度都非常大:例如客户端面临断线重连、网络闪断、心跳处理、半包读写、网络拥塞和异常流的处理等等。Netty对JDK自带的NIO的API进行......
  • Netty源码学习2——NioEventLoop的执行
    系列文章目录和关于我零丶引入在《Netty源码学习1——NioEventLoopGroup的初始化》中,我们学习了NioEventLoopGroup和NioEventLoop的初始化,在下面netty服务端启动的demo中会在ServerBootStrap中指定Channel为Nio类型的Channel,然后启动的时候绑定端口,之前我们解释道NioEventLoop......
  • for循环中使用setTimeout得到的结果
    for(varindex=0;index<5;index++){setTimeout(()=>{console.log(index)},1000)}//输出5个5for(letindex=0;index<5;index++){setTimeout(()=>{......
  • Vue学习笔记:Vuex Part04 Getter
    Getter可以将store的state派生出一些状态,比如根据条件进行过滤Getter接受state作为其第一个参数,示例:conststore=createStore({state:{todos:[{id:1,text:'...',done:true},{id:2,text:'...',done:false}]},getters:{......
  • springboot 打包 时报错:The specified user settings file does not exist: F:\opt\
     解决方法:  ......
  • Could not find a generator for route RouteSettings("search", null) in the _Widge
    遇到这个错误消息意味着在您的Flutter应用程序中没有为名为"search"的路由定义路由生成器。要解决此问题,您需要定义一个路由生成器来处理名为"search"的路由。以下是如何在Flutter应用程序中定义路由生成器的示例:首先,定义一个路由生成器函数,该函数接受 RouteSettings 对象并返回......
  • Kettle 连接失败 Oracle 数据库报 ora-12505 的解决方法(转)
      用kettle新建DB连接的时候总是报错,可是用plsql连接是可以连上,错误信息大致如下:错误连接数据库[MIS]:org.pentaho.di.core.exception.KettleDatabaseException:ErroroccuredwhiletryingtoconnecttothedatabaseErrorconnectingtodatabase:(usingclassorac......