第一次写线段树分治

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define per(i,a,b) for(int i=(a),i##end=(b);i>=i##end;i--)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=800005;
int n,m,k,fa[2*N],siz[2*N],st;
struct node{
	int a,b,c;
}s[N];
struct T{
	int l,r;
	vector <pair<int,int> > v;
}t[N<<2];
inline int findfa(int x) {while(x^fa[x]) x=fa[x];return x;}
inline void unionn(int x,int y){
	if(x==y) return;
	if(siz[x]<siz[y]) swap(x,y);
	s[++st]=node{x,y,siz[y]},siz[x]+=siz[y],fa[y]=x;
}
inline void undo(){
	int a=s[st].a,b=s[st].b,c=s[st].c;
	st--;
	fa[b]=b,siz[a]-=c;
}
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return f*x;
}
inline void build(int rt,int l,int r){
	t[rt].l=l,t[rt].r=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}
inline void add(int rt,int l,int r,int x,int y){
	if(l<=t[rt].l&&t[rt].r<=r) return t[rt].v.push_back(make_pair(x,y)),void();
	if(t[rt<<1].r>=l) add(rt<<1,l,r,x,y);
	if(t[rt<<1|1].l<=r) add(rt<<1|1,l,r,x,y);
}
inline void dfs(int rt){
	int tmp=st,flag=0;
	for(auto u:t[rt].v){
		int a=u.first,b=u.second;
		if(findfa(a+n)==findfa(b+n)||findfa(b)==findfa(a)){
			rep(i,t[rt].l,t[rt].r) printf("No\n");
			flag=1;
			break;
		}
		unionn(findfa(a),findfa(b+n));
		unionn(findfa(b),findfa(a+n));
	}
	if(flag==0){
		if(t[rt].l==t[rt].r) printf("Yes\n");
		else{
			dfs(rt<<1);
			dfs(rt<<1|1);
		}
	}
	while(st>tmp) undo();
}
int main(){
	n=read(),m=read(),k=read();
	rep(i,1,2*n) fa[i]=i;
	build(1,1,k);
	rep(i,1,n){
		int x=read(),y=read(),z=read(),w=read();
		if(z==w) continue;
		add(1,z+1,w,x,y);
	}
	dfs(1);
	return 0;
}