线段树分治

绪论

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

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

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

例题

题面和数据范围

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

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

解法

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

另外的

详见：bzoj4025和bzoj3237。