并查集、线段树分治
考虑二分图的判定，无法应用黑白染色，使用并查集维护。
具体地，初始化并查集，使用 $\operatorname{ask}(i)$ 表示 $i$ 在并查集中的祖宗编号。维护 $e_i$ 表示节点 $i$ 的一个邻点，枚举到边 $(u,v)$ 时如果 $\operatorname{ask}(u) = \operatorname{ask}(v)$ 则说明当前图不是二分图；否则合并 $u,e_v$ 所在的两个集合以及 $e_u,v$ 所在的两个集合。并查集实质上维护的是不能与节点 $i$ 连边的节点的集合，因为它们同属于二分图的左/右部点。
由于无法利用撤销操作完全模拟整个过程，不能应用可持久化并查集。
考虑线段树分治，由于应用线段树分治，不能使用均摊时间复杂度 $O(n \log n)$ 的路径压缩并查集，因为可以构造操作把一次查询操作的时间复杂度卡到 $O(n)$，后续只需要重复撤销和加入这次操作就可以将程序的时间复杂度卡到 $O(n^2)$。具体地，每次把 $i$ 合并到 $i+1$，最后会得到一条 $1 \sim n$ 的链，这时调用 $\operatorname{ask}(1)$ 的时间复杂度为 $O(n)$。使用按秩合并优化的并查集。并查集是对全局开的，每次撤销肯定撤销最后一次操作，可以用栈维护。
如果执行完毕当前节点操作后图不是二分图，那么当前节点表示的区间 $[l,r]$ 内所有时刻的答案都是 No，无需向下递归。注意题目中有时刻 $0$ 就存在的边和从未存在过的边，将输入的 $l,r$ 加一后处理。另外自环会直接导致整个图不是二分图。
由于 $n,k$ 同阶，时间复杂度 $O(m \log^2 n)$。
#include<bits/stdc++.h>
using namespace std;
struct DSU{
int cnt,f[100'005],w[100'005],sf[100'005],sx[100'005],sy[100'005],sw[100'005];
void resize(int n){
cnt=0;
for(int i=1;i<=n;i++) f[i]=i,w[i]=1;
}
int ask(int x){
while(x!=f[x]) x=f[x];
return x;
}
bool merge(int x,int y){
x=ask(x),y=ask(y);
if(x==y) return 0;
if(w[x]>w[y]) swap(x,y);
++cnt,sx[cnt]=x,sy[cnt]=y;
sf[cnt]=f[x],sw[cnt]=w[y];
f[x]=y,w[y]+=(w[x]==w[y]);
return 1;
}
void rollback(int x){
for(int i=1;i<=x;i++){
f[sx[cnt]]=sf[cnt];
w[sy[cnt]]=sw[cnt];
--cnt;
}
}
}dsu;
struct Edge{int x,y;Edge(int _x,int _y):x(_x),y(_y){}};
vector<Edge> v[400'005];
vector<int> c[400'005];
int n,m,k,e[100'005];
bool ans[100'005];
void update(int u,int l,int r,int ql,int qr,Edge x){
if(l>=ql&&r<=qr) return v[u].push_back(x);
int mid=(l+r)>>1;
if(ql<=mid) update(u*2,l,mid,ql,qr,x);
if(qr>mid) update(u*2+1,mid+1,r,ql,qr,x);
}
void segsort(int u,int l,int r){
int cnt=0,mid=(l+r)>>1;
for(auto i:v[u]){
if(dsu.ask(i.x)==dsu.ask(i.y)) goto warp;
if(e[i.x]==0) e[i.x]=i.y,c[u].push_back(i.x);
if(e[i.y]==0) e[i.y]=i.x,c[u].push_back(i.y);
if(dsu.merge(i.x,e[i.y])) ++cnt;
if(dsu.merge(e[i.x],i.y)) ++cnt;
}
if(l==r) ans[l]=1;
else segsort(u*2,l,mid),segsort(u*2+1,mid+1,r);
warp:for(int j:c[u]) e[j]=0;
dsu.rollback(cnt);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
dsu.resize(n);
for(int i=1;i<=m;i++){
static int x,y,l,r;
scanf("%d%d%d%d",&x,&y,&l,&r);
if(l==r) continue;
++l,++r;
update(1,1,k,l,r-1,Edge(x,y));
}
segsort(1,1,k);
for(int i=1;i<=k;i++) puts(ans[i] ? "Yes":"No");
return 0;
}