点此看题面
大致题意： 给你一张图以及每条边的出现时间和消失时间，让你求每个时间段这张图是否是二分图。
二分图有一个比较简单的性质，即二分图中不存在奇环。
于是题目就变成了：让你求每个时间段这张图是否不存在奇环。
关于，详见这篇博客：LCT入门。
接下来我们开始讨论如何用动态维护图连通性。
动态维护树连通性，应该是比较简单，因为本身就是一棵树，加边删边都很容易。
而维护图连通性最麻烦的一点，就是在于会出现环，而这样就无法按照一般的方式来加边删边了。
那么，有没有什么办法，使得既能维护图连通性，又不会使上出现环呢？
这时就有一个比较贪心的想法。
考虑到每条边最后都是要删掉的，那么当构成环时，我们就可以将该环中最早要被删掉的边给删去，因为这样一来不会影响连通性，二来又可以化环为链，十分巧妙。
但这个方法唯一美中不足的地方就在于，它是一个离线算法，遇上强制在线就无能为力。
不过，这题可以离线做，就没有问题了。
具体实现过程中，我们可以把边看作节点，记录下被删的时间（真正的点被删除时间可设为）。
每个节点记录下该子树内被删时间最早的节点编号，出现环时将会构成环的那条链抠出，然后更新即可。
接下来我们要考虑如何维护奇环个数。
我们可以记录下每个节点子树内有多少条边，当出现环时，判断是否为奇环，若是则将计数器加。同理，当删除环时，判断是否为奇环，若是则将计数器减。输出答案时判断计数器是否为即可。
#include<bits/stdc++.h>
#define Type template<typename I>
#define N 100000
#define M 200000
#define swap(x,y) (x^=y^=x^=y)
#define INF 1e9
using namespace std;
int n,m,t,flag,tag[N+M+5];
struct Operate
{
int x,y,pos,Begin,End;
}o1[M+5],o2[M+5];
class Class_FIO
{
private:
#define Fsize 100000
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)
char ch,*A,*B,Fin[Fsize];
public:
Class_FIO() {A=B=Fin;}
Type inline void read(I& x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
template<typename I,typename... A> inline void read(I& x,A&... y) {read(x),read(y...);}
}F;
class Class_LCT//LCT动态维护图连通性
{
private:
#define SIZE (N+M)
#define PushUp(x)//上传子节点信息
(
node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+(x>n),node[x].Min=x,
Val[node[x].Min]>Val[node[node[x].Son[0]].Min]&&(node[x].Min=node[node[x].Son[0]].Min),
Val[node[x].Min]>Val[node[node[x].Son[1]].Min]&&(node[x].Min=node[node[x].Son[1]].Min)
)
#define Rever(x) (swap(node[x].Son[0],node[x].Son[1]),node[x].Rev^=1)
#define PushDown(x) (node[x].Rev&&(Rever(node[x].Son[0]),Rever(node[x].Son[1]),node[x].Rev=0))
#define Which(x) (node[node[x].Father].Son[1]==x)
#define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)
#define IsRoot(x) (node[node[x].Father].Son[0]^x&&node[node[x].Father].Son[1]^x)
#define MakeRoot(x) (Access(x),Splay(x),Rever(x))
#define Split(x,y) (MakeRoot(x),Access(y),Splay(y))
int Stack[SIZE+5];
struct Tree
{
int Min,Size,Rev,Father,Son[2];
}node[SIZE+5];
inline void Rotate(int x)
{
register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);
!IsRoot(fa)&&(node[pa].Son[Which(fa)]=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1),PushUp(fa),PushUp(x);
}
inline void Splay(int x)
{
register int fa=x,Top=0;
while(Stack[++Top]=fa,!IsRoot(fa)) fa=node[fa].Father;
while(Top) PushDown(Stack[Top]),--Top;
while(!IsRoot(x)) fa=node[x].Father,!IsRoot(fa)&&(Rotate(Which(x)^Which(fa)?x:fa),0),Rotate(x);
}
inline void Access(int x) {for(register int son=0;x;x=node[son=x].Father) Splay(x),node[x].Son[1]=son,PushUp(x);}
public:
int Val[SIZE+5];
Class_LCT() {Val[0]=INF;}
inline void Init(int len) {for(register int i=1;i<=len;++i) Val[i]=INF,node[i].Min=i;}//将真正的点被删除时间设为INF
inline void Link(int x,int y) {MakeRoot(x),FindRoot(y)^x&&(node[x].Father=y);}
inline void Cut(int x,int y) {MakeRoot(x),!(FindRoot(y)^x)&&!(node[y].Father^x)&&!node[y].Son[0]&&(node[y].Father=node[x].Son[1]=0,PushUp(x));}
inline int FindRoot(int x)
{
Access(x),Splay(x);
while(node[x].Son[0]) PushDown(x),x=node[x].Son[0];
return Splay(x),x;
}
inline int QueryMin(int x,int y) {return Split(x,y),node[y].Min;}//查询子树内最早被删除的边的编号
inline int QuerySize(int x,int y) {return Split(x,y),node[y].Size;}//查询子树内有多少条边
#undef SIZE
}LCT;
inline bool cmp1(Operate x,Operate y) {return x.Begin<y.Begin;}//将边按出现时间排序
inline bool cmp2(Operate x,Operate y) {return x.End<y.End;}//将边按消失时间排序
inline void Add(int pos)//加入一条边
inline void Del(int pos)//删除一条边
int main()
{
register int i,p1=1,p2=1;
for(F.read(n,m,t),LCT.Init(n+m),i=1;i<=m;++i) F.read(o1[i].x,o1[i].y,o1[i].Begin,o1[i].End);//读入
for(sort(o1+1,o1+m+1,cmp1),i=1;i<=m;++i) o1[i].pos=n+i,o2[i]=o1[i];
for(sort(o2+1,o2+m+1,cmp2),i=1;i<=t;++i)
{
while(p1<=m&&o1[p1].Begin<i) Add(p1++);while(p2<=m&&o2[p2].End<i) Del(p2++);//加入和删除边
puts(flag?"No":"Yes");//判断是否有奇环，输出答案
}
return 0;
}
