P5787 二分图 /【模板】线段树分治
传送门
分析：
\(1\)、并查集判断二分图：
定义\(2n\)个点，染成黑白两色，代表两个不同的集合，\(a_1\)与\(a_{1+n}\)为不同的颜色，以此类推，对于\(a_i\)和\(a_j\)的连边，判断\(a_i\)和\(a_j\)是否属于同一集合，若属于，则该图不是二分图；否则\(a_i\)的并查集和\(a_{j+n}\)的并查集合并，\(a_j\)的并查集和\(a_{i+n}\)的并查集合并。
证明正确性：
对于\(i,j\leq n\)，若\(a_i\)和\(a_j\)属于同一个集合，则从\(a_i\)到\(a_j\)的边数必然为偶数个，因为每到一个小于\(n\)的点必然会经过一个大于\(n\)的点（我们是这么构造的，所有小于\(n\)的点都只与大于\(n\)的连边），因为\(i,j\leq n\)，所以\(a_i\)到\(a_j\)的路径中（不包括\(a_i,a_j\)）有\(k\)个大于\(n\)的点，有\(k-1\)个小于\(n\)的点，共有\(2k\)条边，满足二分图的定义：二分图中不存在长度为奇数的环。
再将\(a_i\)与\(a_j\)为同一并查集解释为\(a_i\)和\(a_j\)为在同一集合，\(a_i\)与\(a_{j+n}\)为同一并查集解释为\(a_i\)和\(a_j\)不在同一集合即可。
证毕。
\(2\)、线段树分治
核心思想：离线在时间轴上建立线段树，对于每个操作，定义为线段树内的区间操作，然后遍历线段树输出答案
目的：在低时间复杂度内解决一类在线算法并不优秀的问题
这个不好说思路，在代码中体现
\(3\)、可撤销并查集
因为每条边只存在一定时间，所以并查集要支持回溯，所以不能用路径压缩，要用按秩合并
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=4e6+50;
ll n,m,k,top;
struct E{ll x,y;}e[N];
struct jgt{ll x,y,add;}st[N];
vector<ll> t[N];
ll fa[N],h[N];
ll find(ll x)
{
while(x!=fa[x]) x=fa[x];
return fa[x];
}
void add(ll wz,ll l,ll r,ll le,ll ri,ll ti)
{
if(le<=l&&ri>=r)
{
t[wz].push_back(ti);
return ;
}
ll mid=(l+r)/2;
if(le<=mid) add(wz*2,l,mid,le,ri,ti);
if(ri>mid) add(wz*2+1,mid+1,r,le,ri,ti);
}
void merge(ll x,ll y)
{
ll fx=find(x),fy=find(y);
if(h[fx]>h[fy]) swap(fx,fy);
st[++top]={fx,fy,h[fx]==h[fy]};
fa[fx]=fy;
if(h[fx]==h[fy]) h[fy]++;
}
void BT(ll wz,ll l,ll r)
{
bool flag=true;
ll lasttop=top;
for(ll i=0;i<t[wz].size();i++)
{
ll a=find(e[t[wz][i]].x);
ll b=find(e[t[wz][i]].y);
if(a==b)
{
for(ll k=l;k<=r;k++)
puts("No");
flag=false;
break;
}
merge(e[t[wz][i]].x,e[t[wz][i]].y+n);
merge(e[t[wz][i]].y,e[t[wz][i]].x+n);
}
if(flag)
{
if(l==r) puts("Yes");
else
{
ll mid=(l+r)/2;
BT(wz*2,l,mid);
BT(wz*2+1,mid+1,r);
}
}
while(top>lasttop)
{
h[fa[st[top].y]]-=st[top].add;
fa[st[top].x]=st[top].x;
top--;
}
return ;
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&k);
for(ll i=1;i<=m;i++)
{
ll l,r;
scanf("%lld %lld",&e[i].x,&e[i].y);
scanf("%lld %lld",&l,&r);
l++;
add(1,1,k,l,r,i);
}
for(ll i=1;i<=2*n;i++) fa[i]=i,h[i]=1;
BT(1,1,k);
return 0;
}