【oSo的题解】题解：P5787 二分图 /【模板】线段树分治

题目：P5787 二分图 /【模板】线段树分治

前言

一个挺简洁巧妙的离线（是的强制在线用不了）小技巧，我竟然看懂了。
题意

给出 $n$ 个点，$m$ 条出现时间为 $(l,r]$ 的边，求在 $[1,k]$ 每一时刻，该图是否为二分图。
分析

前置芝士：扩展域并查集（种类并查集）、可撤销并查集（本题不需要可持久化并查集哦）、线段树。
Part-0

首先先说一下如何判断二分图。
我们先开一下每个点的反集，即对于一个点 $u$，所有与 $u$ 相连的点 $v$，都在 $u+n$ 这个集合里。
然后每加入一条边时，考虑到只有边的两个顶点可能会发生冲突，就 find 一下是否在同一集合中，不在就相互加反集，在就没有必要继续处理了直接往回撤销。
Part-1

那该怎么维护加边和删边呢？
注意到我们不喜欢删边，会造成极大的时间开销，于是可以通过撤销上一次合并操作来达成删边的目的。
而加边就是普通的合并操作。
因为要求我们输出每一时刻的答案，我们可以沿着时间轴来处理询问。
Part-2

如何维护对于某一时间戳上的所有操作？
我们观察到如果只是普通地从前向后扫时间轴，拿到了下一个点及不知道该如何撤销，又不知道该加什么边。
我们可以考虑树形的数据结构。
我们可以对于每一时刻认为是一个独立的叶子节点，然后建线段树。
线段树每一节点都储存着一些操作，这些操作的出现时间均包含该节点的时间段，即相当于每一个节点上的 tag 记录了这一时间段存在的边。
然后我们可以通过类似于区间加的方式，将每一段的出现时间打在线段树上。
Part-3

那我们如何获取答案呢？
观察到，对于每一时刻的答案，即每个叶子的答案，是判断从线段树的根节点到该节点的路径上所有经过点包含的 tag 打在一起的图是否为二分图。
那么我们考虑从根节点进行 dfs，每到一个点就根据 Part-0 判断到目前为止的图是否为二分图，如果不是就没有搜的必要了，可以直接回溯。
代码细节提醒

要注意可撤销并查集只能写按秩合并，不要写路径压缩。
注意当不是二分图需要回溯时一定要先撤销再回溯。
撒花。
AC Code

[code]#include#define int long long #define rep(I,A,B) for(int I=(A);I=(B);--I)#define el puts("")#define Yuki return #define daisuki 0using namespace std;using pii=pair;//码风丑还请见谅捏//代码已经被我分成了小部分，可以按照每个部分进行debug//不要直接复制粘贴我的代码谢谢哈//fastIO starttemplatevoid read(T &x){  x=0;bool f=0;char c=getchar();  for(;!isdigit(c);c=getchar())if(c=='-')f=1;  for(;isdigit(c);c=getchar())x=(x