线段树分治

seekerhit 2019-10-19

绪论

这个算法借助线段树,然后事实上是通过遍历线段树进行分治。

先用一种比较容易的方式来解释吧。

先回忆天天爱跑步一类的题目,大致就是在一棵树上通过DFS,访问到这个点的时候把这个点上的操作加入贡献,离开的时候除去贡献,然后就可以了。当我们发现一个操作不能只用一个点来表示,也即,两个操作有交却又不完全包含,就把两个操作有相交的属性(通常是时间)作为线段树的索引对象,然后把每个操作拆分成 \(log\) 个操作,然后就可以套用前面说的方法了(当然维护方法有所不同)。

例题

题面和数据范围

地理课上,老师给出了一个巨大的地图,由于世界日新月异,会有一些道路在某一时刻被删除,也会有一些道路在某一时刻被修建。这里的道路均为双向的。老师认为,有一些城市被分在了一个连通块中可以相互到达,而有一些城市不能够相互到达。而他想知道,每个时刻所有连通块大小的乘积是多少?小A看到这个地图的时候就蒙了,还好那只上天的喵及时帮助了他。现在他把这个清真的地图拿过来给你,想试试看你能不能求出来。由于答案可能很大,输出乘积 \(\mod 10^9+7\) 即可。

\(n,m\leq 100000\) ,保证无重边、自环。

解法

显然,先按照之前的部分把每个询问放到树上,然后对整棵线段树做一次DFS,然后用可撤销并查集维护一下,就能得到答案。

另外的

详见:bzoj4025bzoj3237

相关推荐