```cpp
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
const int SIZE=1e5+10;
struct EDGE{
int u,v;
};
struct stuse{
int a,b;
int dada,dadb;
int rnka,rnkb;
};
struct DSU{
int dad[SIZE<<1];
int rnk[SIZE<<1];
stack<stuse> st;
void init(int MAXN){
for(int i=1;i<=MAXN;i++)
dad[i]=i,rnk[i]=1;
}
int anc(int x){
while(x^dad[x]) x=dad[x];
return x;
}
bool ask(int x,int y){
return anc(x)==anc(y);
}
void uni(int x,int y){
x=anc(x),y=anc(y);
stuse tmp;//记录合并信息
if(rnk[x]>rnk[y])
{
tmp.dada=dad[x];//将b合并至a上
tmp.dadb=dad[y];
tmp.a=x;
tmp.b=y;
tmp.rnka=rnk[x];
tmp.rnkb=rnk[y];
dad[y]=x;
rnk[x]=max(rnk[y]+1,rnk[x]);
}
else
{
tmp.dada=dad[y];
tmp.dadb=dad[x];
tmp.a=y;
tmp.b=x;
tmp.rnka=rnk[y];
tmp.rnkb=rnk[x];
dad[x]=y;
rnk[y]=max(rnk[x]+1,rnk[y]);
}
st.push(tmp);
}
bool back(){
if(st.empty()) return false;
stuse tmp=st.top();
dad[tmp.b]=tmp.dadb;
rnk[tmp.a]=tmp.rnka;//回溯信息
st.pop();
return true;
}
}union_set;
struct Laffey{
int ls,rs;
vector<EDGE> e;
void insert_edge(EDGE E){
e.push_back(E);
}
#define ls(i) (tree[i].ls)
#define rs(i) (tree[i].rs)
}tree[SIZE<<5];
int postot;
void add(int nl,int nr,int l,int r,int &i,EDGE e){
if(!i) i=++postot;
if(nl>=l&&nr<=r)
{
tree[i].insert_edge(e);//加边
return ;
}
int mid=(nl+nr)>>1;
if(mid>=l) add(nl,mid,l,r,ls(i),e);
if(mid+1<=r) add(mid+1,nr,l,r,rs(i),e);
}
bool ans[SIZE];
void cpy(int l,int r){
//保存答案
for(int i=l;i<=r;i++)
ans[i]=true;
}
int n;
void getans(int nl,int nr,int i){
if(!i)
{
cpy(nl,nr);
return ;
}
for(int _=0;_<(int)tree[i].e.size();_++)
{
EDGE edge=tree[i].e[_];// 依次加边
if(union_set.ask(edge.u,edge.v))
{
for(int j=0;j<_;j++)
union_set.back(),union_set.back();
return ;
}
union_set.uni(edge.u+n,edge.v),union_set.uni(edge.u,edge.v+n);
}
if(nl==nr)
{
cpy(nl,nr);
return ;
}
int mid=(nl+nr)>>1;
getans(nl,mid,ls(i));
getans(mid+1,nr,rs(i));
for(int _=0;_<(int)tree[i].e.size();_++)
union_set.back(),union_set.back();//需要回溯两次
}
int main(){
int m,k;
scanf("%d%d%d",&n,&m,&k);
union_set.init(n<<1);
int treert=0;
for(int i=1;i<=m;i++)
{
int u,v,l,r;
scanf("%d%d%d%d",&u,&v,&l,&r);
l++;
if(l>r) continue;
EDGE e=(EDGE){u,v};
add(1,k,l,r,treert,e);
}
getans(1,k,treert);
for(int i=1;i<=k;i++)
puts(ans[i]?"Yes":"No");
return 0;
}
```
by LordLaffey @ 2022-07-15 11:10:42
@[LGod·Laf·Sage](/user/335136) 什么是“冰茶姬”？听起来听高科技的，但bdfs无果
by inc1ude_c @ 2022-07-15 11:30:25
@[__include__](/user/537687) 并查集
by Nt_Tsumiki @ 2022-07-15 11:39:58