#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int root;
int bxj[200010];
int cnt=0;
struct EDGE{
int x,y;
bool operator<(const EDGE &b)const{
if(x!=b.x)return x<b.x;
else return y<b.y;
}
};
stack<EDGE> cx;
map <EDGE,int> num;
int find(int x){
if(bxj[x]==x)return x;
else return find(bxj[x]);
}
bool unionn(int x,int y){
int p=100000;
if(find(x)!=find(y)){
cx.push({find(x),find(y)});
num[cx.top()]++;
bxj[find(x)]=find(y+p);
bxj[find(y)]=find(x+p);
return true;
}
else{
return false;
}
}
void slipt(int x,int y){
int p=100000;
bxj[x]=x,bxj[y]=y;
return;
}
struct tree{
int fa;
int left,right;
int lid,rid;
vector<EDGE> edge;
}leaf[400005];
int build_tree(int l,int r,int fa){
int id=++cnt;
leaf[id].fa=fa;
leaf[id].left=l,leaf[id].right=r;
if(l==r){
return id;
}
int mid=(l+r)/2;
leaf[id].lid=build_tree(l,mid,id);
leaf[id].rid=build_tree(mid+1,r,id);
return id;
}
void add_edge(int x,int y,int l,int r,int id){
if(leaf[id].right<=r and leaf[id].left>=l){
leaf[id].edge.push_back({x,y});
return;
}
int mid=(leaf[id].left+leaf[id].right)>>1;
if(mid>=l)add_edge(x,y,l,r,leaf[id].lid);
if(mid<r)add_edge(x,y,l,r,leaf[id].rid);
return;
}
void dfs(int id,bool bl){
for(auto i:leaf[id].edge){
if(!unionn(i.x,i.y))bl=0;
}
if(leaf[id].left!=leaf[id].right){
dfs(leaf[id].lid,bl);
dfs(leaf[id].rid,bl);
}
else{
if(bl)cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
for(int i=0;i<leaf[id].edge.size();i++){
if(!(--num[cx.top()]))slipt(cx.top().x,cx.top().y);
cx.pop();
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
root=build_tree(1,k,cnt);
for(int i=1,x,y,l,r;i<=m;i++){
cin>>x>>y>>l>>r;
add_edge(x,y,l,r,root);
}
dfs(root,1);
return 0;
}
第一次学,没有完全学会