JZOJ4739. 【雅礼联考GDOI2017模拟9.2】Ztxz16学图论（2017.8B组）

https://jzoj.net/senior/#main/show/4739

大意：

给你一些边，然后每次询问添加[l..r]的边后图内有多少个联通块

想法：

用并查集做，LCT维护即可

然而我比较弱，所以我拿出了十分优美的暴力莫队

但好像不可行

我们只需要用到莫队的分块思想，离线处理每一个询问

先按l端点从小到大分块（因为要均摊时间复杂度这里要用sqrt（m/log(m)）））,再对每个块，按照右端点从小到大排序

然后对于每个块里面，由于每个块只是右端点有序，左端点是乱的，对于下个块的第一条边到r[i]，由于r不断递增，这边的并查集可以路径压缩，至于这个块的最后一条边到末尾，我们只能暴力的去维护（或按秩合并，即树高小的父亲变成树高大的），同时把每个改过的节点记录，到下一个询问还原回去就好了

第一次打分块，调了30分钟，思想比较容易