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