题面
Solution
这种每条边出现在一段区间的题，我们可以先考虑使用线段树分治来搞。
这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。
考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。
接下来，我们考虑如何维护一个图是否为二分图的问题。我们知道，一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶数。
知道这一点之后，我们考虑用并查集处理这个问题。对于没有环的时候，我们直接连上就好。对于有环的时候，我们就需要知道这两个点的距离是奇数还是偶数。如果是奇数的，说明之后无论在怎么连，这个图一定gg了，直到这条边取消位置；如果是偶数的，说明这个环是合法的，之后无论有什么边接到这个环上，我们当前这条新插入的边都不会有任何影响。因此，如果一条边会连城环，无论如何，这条边都不会被加上。
所以说，我们这里维护的东西是一个生成树。我们考虑用并查集维护这个生成树。因为我们这里是按秩合并的并查集，失去了原来的树的结构。因此，我们考虑在每个点上维护它到它的父亲的真实距离。我们在连接两个点的时候，我们在并查集上肯定是连接这两个点所在并查集的父亲。这时候，这两个父亲的真实距离一定为这两个点到父亲的真实距离和+1，(这里我们的真实距离和直接暴力算即可，因为并查集按秩合并时，高度不会太大)。
我们查询的时候我们算的是它们两个点到并查集的LCA的真实距离，因为并查集的LCA不一定是它们在原树中的LCA，因此我们这里按真实距离算出来的距离并非它们两的真实距离。但是，我们会发现这里多算的距离一定是2的倍数(两个点同时经过一条边)，因此，我们的奇偶性质还是正确的。
时间复杂度$O(nlog^2n)$
就酱，我们就可以切掉这道题啦ヾ(◍°∇°◍)ﾉﾞ
Code
//BZOJ 4025 二分图
//线段树二分+并查集妙题
//Mar,25th,2019
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=100000+100;
struct edge
{
int s,t;
edge (int x,int y)
{
s=x,t=y;
}
};
struct UnF
{
int fa[N],size[N],dis[N],depth[N],top,mstack[N*20];
void Init(int n)
{
for(int i=1;i<=n;i++)
depth[i]=size[i]=1;
}
int GetFa(int x,int &w)
{
if(fa[x]==0)
{
w++;
return x;
}
int t=GetFa(fa[x],w+=dis[x]+1);
depth[x]=depth[fa[x]]+1;
return t;
}
int LCA(int x,int y,int &w)
{
w=1;
if(depth[x]<depth[y]) swap(x,y);
while(depth[x]>depth[y])
w+=dis[x]+1,x=fa[x];
if(x==y) return x;
w++;
while(fa[x]!=fa[y])
{
w+=dis[x]+1,w+=dis[y]+1;
x=fa[x],y=fa[y];
}
w+=dis[x]+dis[y]+1;
return fa[x];
}
int Link(int x,int y)
{
int d1=0,d2=0,fa1=GetFa(x,d1),fa2=GetFa(y,d2);
if(size[fa1]>size[fa2])
swap(x,y),swap(fa1,fa2),swap(d1,d2);
mstack[++top]=0;
//cerr<<fa1<<" "<<fa2<<" "<<x<<" "<<y<<" "<<d1<<" "<<d2<<endl;
if(fa1==fa2)
{
int t_d=0;
LCA(x,y,t_d);
if(t_d%2==1)
return 1;
return 0;
}
mstack[top]=fa1;
dis[fa1]=d1+d2-2,fa[fa1]=fa2,size[fa2]+=size[fa1];
return 0;
}
void Undo()
{
if(mstack[top]!=0)
size[fa[mstack[top]]]-=size[mstack[top]],fa[mstack[top]]=0,
dis[mstack[top]]=0,depth[mstack[top]]=1;
top--;
}
}unf;
int ans[N],top,OK;
struct SegmentTree
{
#define mid ((now_l+now_r)>>1)
#define lson (now<<1)
#define rson (now<<1|1)
vector <edge> w[N<<2];
void Add(int l,int r,edge x,int now,int now_l,int now_r)
{
if(now_l>=l and now_r<=r)
{
w[now].push_back(x);
return;
}
if(l<=mid) Add(l,r,x,lson,now_l,mid);
if(r>mid) Add(l,r,x,rson,mid+1,now_r);
}
void dfs(int now,int now_l,int now_r)
{
int cnt=0;
for(int i=0;i<int(w[now].size());i++)
cnt+=unf.Link(w[now][i].s,w[now][i].t);
OK+=cnt;
//cerr<<endl;
//cerr<<now<<" "<<now_l<<" "<<now_r<<" "<<cnt<<endl;
if(now_l==now_r)
ans[now_l]=OK;
else
{
dfs(lson,now_l,mid);
dfs(rson,mid+1,now_r);
}
OK-=cnt;
for(int i=0;i<int(w[now].size());i++)
unf.Undo();
}
#undef mid
#undef lson
#undef rson
}sgt;
int n,m,q;
int main()
{
n=read(),m=read(),q=read();
unf.Init(n);
for(int i=1;i<=m;i++)
{
int u=read(),v=read(),s=read(),t=read();
sgt.Add(s+1,t,edge(u,v),1,1,q);
}
sgt.dfs(1,1,q);
for(int i=1;i<=q;i++)
if(ans[i]==0)
printf("Yes\n");
else
printf("No\n");
return 0;
}