P5787 二分图 /【模板】线段树分治
普通二分图：染色
染色无法扩展，先考虑加边
如果两点在同一联通块内：加边只需要考虑连边的两个点颜色是否相同
如果不在同一联通块内，第一次加边为 YES，合并联通块，接下来的操作同上
再考虑删边
线段树分治思想
解决问题：容易插入，难删除，且插入顺序不影响结果
如果一个图是二分图，当且仅当它不是奇环；如果没有奇环，则一定是二分图
把在 \(l\) 插入、在 \(r\) 删除理解为在 \([l,r]\) 存在
暴力做法：每一个时间刻都是空图，分别插入此时存在的边
并查集判断奇环，对于每个点 \(i\) 建立一个虚点 \(n+i\)，\(u\) 到 \(v\) 的连边变为 \(u\) 到 \(v+n\) 和 \(v\) 到 \(u+n\)，此时只需判断 \(u\) 和 \(u+n\) 是否联通，如果联通则为二分图，否则不是二分图
把一个线段存在的时间挂在线段树上
既不能做删除操作，又想优化复杂度做继承操作（当前时间点继承上一个时间点的操作）
一个节点继承其父亲的情况，可以做到不需要删除
但是需要 dfs，此时又不可避免的回溯 return，即仍然需要删除
考虑规避掉删除，和之前的删除的区别是，此次删除是可撤销的
-
不想要删除，将删除变为插入和撤销
-
插入：将时间段扔到类似线段树的分治结构
-
撤销：在分治结构上
dfs，进行撤销操作
问题在于并查集如何撤销路径压缩的操作，并查集是不可撤销的，这个性质取决于其时间复杂度
标签：二分,联通,进阶,删除,线段,撤销,插入 From： https://www.cnblogs.com/CheZiHe929/p/18263089