[CodeChef GERALD07/BZOJ3514]Codechef MARCH14 GERALD07[加强版](LCT,主席树)

发布于 2018-01-27  240 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[CodeChef GERALD07/BZOJ3514]Codechef MARCH14 GERALD07[加强版](LCT,主席树)

Description

N个点M条边的无向图,询问保留图中编号在[l,r]的边的时候图中的联通块个数。

Http

Codechef
BZOJ

Tag

LCT,主席树

解决思路

原题没有强制在线,加强版有,我们直接讨论加强版的做法。
考虑一条边\(u->v\),若加入它之前\(u,v\)不连通,那么加入它之后,连通块个数减一;否则,连通块个数不变,但图中出现了一个环,此时,我们去掉这个环中最早加入的边,记\(ntr[i]\)表示加入\(i\)这条边时,去掉的那个最早的边的编号,特别的,若之前\(u,v\)不连通,\(ntr[i]=0\),若为自环,\(ntr[i]=i\)。
求出这个\(ntr\)之后,对于询问\(l,r\)之间的边,我们计算\(l,r\)中\(ntr\)小于\(l\)的有多少个,用总点数\(n\)减去这个个数即为每一次的答案。
这么做为什么是对的呢?由于我们\(ntr\)中记录的是与这一条边形成环的最早的边的编号,那么如果这一条边的\(ntr\)小于\(l\),那么也就是说它一定有减去一个连通块的贡献,否则,它的两个端点已经在一个连通块中了,把它加入不会影响答案。
那么,任务就变成了按照编号顺序依此加边,维护编号尽量大的一棵生成树,这个可以用\(LCT\)维护;至于查询\(l,r\)中\(ntr\)小于\(l\)的个数,可以插入到一棵主席树维护权值线段树。
注意,\(Codechef\)有多组数据,下面的代码是针对\(BZOJ\)的。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[CodeChef GERALD07/BZOJ3514]Codechef MARCH14 GERALD07[加强版](LCT,主席树)


HNCJ OIer