# bzoj4025 二分图（线段树分治+带权并查集维护路径长奇偶性）

## bzoj4025 二分图

n<=100000，m<=200000，T<=100000，1<=u,v<=n，0<=start<=end<=T。

```#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100005;
const int M=200005;
int n,m,T,S[2*M],top=0,fa[N],rank[N],c[N];
struct node
{
int u,v,st,ed;
node(){}
node(int u,int v,int st,int ed):u(u),v(v),st(st),ed(ed){}
};
int getfa(int x)
{
if(fa[x]==x) return x;
else return getfa(fa[x]);
}
int dis(int x)
{
if(fa[x]==x||!fa[x]) return 0;
return c[x]^dis(fa[x]);
}
void merge(int x,int y,int w)
{
if(rank[x]>rank[y]) swap(x,y);
if(rank[x]==rank[y]) {S[++top]=-y; rank[y]++;}
S[++top]=x; fa[x]=y; c[x]=w;
}
void res(int x)
{
while(top>x)
{
if(S[top]<0) rank[-S[top]]--;
else {fa[S[top]]=S[top]; c[S[top]]=0;}
top--;
}
}
void query(int lf,int rg,vector<node> &E)
{
int pre=top; int mid=(lf+rg)>>1;
vector<node> L,R; int sz=E.size();
for(int i=0;i<sz;i++)
{
if(E[i].st==lf&&E[i].ed==rg)
{
int x=E[i].u; int y=E[i].v;
int fx=getfa(x); int fy=getfa(y);
if(fx!=fy)
{
int w=dis(x)^dis(y)^1;
merge(fx,fy,w);
}
else
{
int w=dis(x)^dis(y);
if((w&1)==0) {for(int j=lf;j<=rg;j++) printf("No\n"); res(pre); return;}
}
}
else
{
if(E[i].ed<=mid) L.push_back(E[i]);
else if(E[i].st>mid) R.push_back(E[i]);
else {L.push_back(node(E[i].u,E[i].v,E[i].st,mid));
R.push_back(node(E[i].u,E[i].v,mid+1,E[i].ed));}
}
}
if(lf==rg){printf("Yes\n"); res(pre); return;}
query(lf,mid,L); query(mid+1,rg,R);
res(pre);
}
int main()
{
scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;i++) fa[i]=i,rank[i]=0;
vector<node> e;
for(int i=1;i<=m;i++)
{
int u,v,st,ed; scanf("%d%d%d%d",&u,&v,&st,&ed); st++;
if(st<=ed) e.push_back(node(u,v,st,ed));
}
query(1,T,e);
return 0;
}```