题面 4025: 二分图 Solution 这种每条边出现在一段区间的题，我们可以先考虑使用线段树分治来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，我们考虑如何维护一个图是否为二分图的问题。我们知道，一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶数。 知道这一点之后，我们考虑用并查集处理这个问题。对于没有环的时候，我们直接连上就好。对于有环的时候，我们就需要知道这两个点的…

题面 P4246 [SHOI2008]堵塞的交通 Solution 这题的确是有线段树上大分类讨论的在线做法，但是本菜鸡还是想主要讲一下离线暴力做法。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一个叶子节点的时候，这个叶子节点代表的询…

题面 P5227 [AHOI2013]连通图 Solution 这题可以离线，因此我们可以考虑用线段树分治维护动态图连通性来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一个叶子节点的时候，这个叶子节点代表的询问上所要连的边一定已经…

题面 #121. 「离线可过」动态图连通性 Solution 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，直接在线段树上跑dfs,每到一个区间，就把这个区间里面存的边通通在并查集中连上；每完成一个区间，就把这个区间连上的边通通取消（类似于回溯）。 这样搞，我们每次到一个叶子节点的时候，这个叶子节点代表的询问上所要连的边一定已经全部连上了，直接在并查集中查询即可。 因为我们这里有撤销（回溯）操作…

题面 P3247 [HNOI2016]最小公倍数 Solution 这是一道妙题。 首先，根据常识，题面要我们求的是找一条从s,t的路径，使得路径上$max\ a=a,max\ b=b$。 这咋求呢？我们会发现，我们要求的路径本质上是一个连通块，连通块可以考虑用并查集处理。 接下来考虑对a分块，先把所有的边按照$a$来排序，再分块，每个块里连的所有边保证$<=a_{[size*x]}$，如下图所示： 接下来，我们考虑把所有询问按照b从小到大排序去一个个计算，每计算一个询问之前，把$b<=q[i].b$的…