ssoj3988: 地理课(geography)

题意：一张n个点的无向图，初始无边，每次加入或删掉一条边，询问每次所有联通块大小的乘积。n,m<=1e5.（对1e9+7取模）
题解：
考场时一看就觉得不可做，果断打了暴力后就弃了。考虑若只有加入就很好做，那么能不能将问题转化为只有加入，或者比较好进行删除的呢?只有加入不太可行，考虑删除的困难性在于不知道它的加入影响了什么，那么如果能在加入完后，记录他的影响，就容易删除了。但若直接在线处理，很难高效维护它的影响，故考虑离线。发现对于一条边，它的影响是若干段时间，对于区间问题的维护，就想到线段树，于是将时间段记在线段树中，那么我们要求的是每一个时间点的信息，即叶子节点的信息，也就是从根递归下来的所有标记。那么问题就剩下对线段树上的一个节点，它的标记如何影响后代，及离开它时如何撤回标记的问题。暴力地想，对每条边的标记，用非路径压缩的并查集维护（因为要撤销，故要记录节点的祖先后代关系，所以不能路径压缩），取大小较小的子树合并上去，即启发性合并即可。
TLE警示：启发式合并是将大小较小的那颗树合并上去，而不是大小较小的节点（不知道为什么自己这么脑残，可能第一次写启发式合并吧。。。），以及快速幂要预处理（脑残++）。

转载自：https://blog.csdn.net/sz_165394732/article/details/83719875