rt，kruskal重构树+树状数组，感觉题解的大小跟我开的差不多啊，过了前两个 subtask

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct Node{
	int u,v,val;
}edg[400001];
struct qry{
	int s,t,l,r;
}qr[200001];
struct deal{
	int opt,x,pl,fr,ch;
}q[200001]; 
int fr[400051];
int val[2][200051],dfn[2][200051];
int f[2][200051][21],l[2][200051],r[2][200051];
int a[200051],ans[200051];
int head[2][200051],nex[2][400051],to[2][400051];
int tot,sum,all;
bool cmp(Node x,Node y){
	return x.val<y.val;
}
bool cmp2(Node x,Node y){
	return x.val>y.val;
}
bool cmp3(deal x,deal y){
	return (x.x==y.x?x.opt<y.opt:x.x<y.x);
}
int n,m,cnt;
int find(int x){
	if(x==fr[x]) return fr[x];
	else return fr[x]=find(fr[x]);
}
int lowbit(int x){
	return x&(-x);
}
void add(int x,int val){
	while(x<=n){
		a[x]+=val;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
void adde(int x,int y,int b){
	all++;
	to[b][all]=y;
	nex[b][all]=head[b][x];
	head[b][x]=all;
	all++;
	to[b][all]=x;
	nex[b][all]=head[b][y];
	head[b][y]=all;
}
void build(int x){
	all=0;tot=0;
	for(int i=1;i<=n;i++) val[x][i]=i;
	for(int i=1;i<=2*n;i++) fr[i]=i;
	cnt=n;
	for(int i=1;i<=m;i++){
		int u=find(edg[i].u),v=find(edg[i].v);
		if(u==v) continue;
		fr[u]=++cnt;fr[v]=cnt;
		val[x][cnt]=edg[i].val;
		adde(cnt,u,x);adde(cnt,v,x);
	}
}
void dfs(int b,int x,int fa){
	//cout<<x<<' '<<fa<<endl;;
	f[b][x][0]=fa;
	for(int i=1;i<=20;i++){
		f[b][x][i]=f[b][f[b][x][i-1]][i-1];
	}
	if(x>n) l[b][x]=tot+1;
	else l[b][x]=dfn[b][x]=r[b][x]=++tot;
	for(int i=head[b][x];i;i=nex[b][i]){
		int v=to[b][i];
		if(v==fa) continue;
		dfs(b,v,x);
	}
	if(x>=n) r[b][x]=tot;
	//cout<<x<<' '<<f[b][x][0]<<' '<<l[b][x]<<' '<<r[b][x]<<' '<<b<<' '<<val[b][x]<<endl;
}
int get_anc(int b,int x,int v,int jud){
	for(int i=20;i>=0;i--){
		if(jud==-1){
			if(f[b][x][i] && val[b][f[b][x][i]]>=v) x=f[b][x][i];
		}
		else{
			if(f[b][x][i] && val[b][f[b][x][i]]<=v) x=f[b][x][i];
			//cout<<f[b][x][i]<<' '<<val[b][f[b][x][i]]<<' '<<x<<' '<<b<<' '<<i<<endl;
		}
	}
	//cout<<x<<endl;
	return x;
}
int main(){
	int u,v,Q;
	cin>>n>>m>>Q;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		edg[i].u=u+1;edg[i].v=v+1;edg[i].val=max(u+1,v+1);
	}
	sort(edg+1,edg+m+1,cmp);
	build(0);
	dfs(0,cnt,0);
	for(int i=1;i<=m;i++) edg[i].val=min(edg[i].u,edg[i].v);
	sort(edg+1,edg+m+1,cmp2);
	build(1);
	dfs(1,cnt,0);
	for(int i=0;i<n;i++) q[++sum]=((deal){-1,dfn[1][i],dfn[0][i],0,0});
	for(int i=1;i<=Q;i++){
		cin>>qr[i].s>>qr[i].t>>qr[i].l>>qr[i].r;
		qr[i].s++;qr[i].t++;qr[i].l++;qr[i].r++;
		int fir=get_anc(1,qr[i].s,qr[i].l,-1);
		int sec=get_anc(0,qr[i].t,qr[i].r,1);
		q[++sum]=((deal){1,l[1][fir]-1,l[0][sec]-1,i,1});
		q[++sum]=((deal){1,l[1][fir]-1,r[0][sec],i,-1});
		q[++sum]=((deal){1,r[1][fir],l[0][sec]-1,i,-1});
		q[++sum]=((deal){1,r[1][fir],r[0][sec],i,1});
	}
	sort(q+1,q+sum+1,cmp3);
	for(int i=1;i<=sum;i++){
		if(q[i].pl==0) continue;
		if(q[i].opt==1){
			ans[q[i].fr]+=query(q[i].pl)*q[i].ch;
		}
		else add(q[i].pl,1);
	}
	for(int i=1;i<=Q;i++) cout<<(ans[i]>0)<<endl;
}