没调完呀，感觉代码能力还是有待提高......
写代码一定要讲究结构 + 逻辑性.
如果结构或者逻辑性不好的话是非常非常遭罪的 QAQ......
upd：好像调了 5 分钟就过了
这个问题等价于求：$x$ 能到达一个点集， $y$ 也能到达一个点集，这两个点集是否有交集 ?
由于是否到达只有边权最大/最小值决定，所以就建立两颗 kruskal 重构树，然后判断两个子树是否有交集即可.
判断方式是主席树/树套树.
说实话这种硬核数据结构题反倒比那些 DP 什么的好写，好调.
code:
#include <bits/stdc++.h>
#define N 400009
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
// double check !!!
using namespace std;
int n,m,Q,cnt=0,M;
int v1[N],v2[N],rt[N];
struct UNI
{
int p[N];
void init() { for(int i=0;i<N;++i) p[i]=i; }
int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
}s1,b1;
struct SEG
{
#define lson s[x].ls
#define rson s[x].rs
int tot;
struct data { int sum,ls,rs; } s[N*50];
void build(int &x,int l,int r)
{
x=++tot;
if(l==r) return;
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
}
int update(int x,int l,int r,int p,int v)
{
int now=++tot;
s[now]=s[x];
s[now].sum+=v;
if(l==r) return now;
int mid=(l+r)>>1;
if(p<=mid) s[now].ls=update(s[x].ls,l,mid,p,v);
else s[now].rs=update(s[x].rs,mid+1,r,p,v);
return now;
}
int query(int x,int y,int l,int r,int L,int R)
{
if(!x) return 0;
if(l>=L&&r<=R) return s[y].sum-s[x].sum;
int mid=(l+r)>>1,re=0;
if(L<=mid) re+=query(s[x].ls,s[y].ls,l,mid,L,R);
if(R>mid) re+=query(s[x].rs,s[y].rs,mid+1,r,L,R);
return re;
}
#undef lson
#undef rson
}se;
struct SMA
{
int x,y;
SMA(int x=0,int y=0):x(x),y(y){}
bool operator<(const SMA b) const { return min(x,y)>min(b.x,b.y); }
}sm[N];
struct BIG
{
int x,y;
BIG(int x=0,int y=0):x(x),y(y){}
bool operator<(const BIG b) const { return max(x,y)<max(b.x,b.y); }
}bi[N];
struct G
{
int edges,tim;
int bin[N<<1];
int hd[N<<1],to[N<<1],nex[N<<1],st[N<<1],ed[N<<1],fa[20][N<<1];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void dfs(int x)
{
++tim;
st[x]=tim,bin[tim]=x;
for(int i=1;i<20;++i) fa[i][x]=fa[i-1][fa[i-1][x]];
for(int i=hd[x];i;i=nex[i]) fa[0][to[i]]=x,dfs(to[i]);
ed[x]=tim;
}
}G1,G2;
// 递减，即寻找最靠上大于等于 val 的
int get_sm(int x,int val)
{
for(int i=19;i>=0;--i) if(G1.fa[i][x]&&v1[G1.fa[i][x]]>=val) x=G1.fa[i][x];
return x;
}
// 递增，即寻找最靠上小于等于 val 的
int get_bi(int x,int val)
{
for(int i=19;i>=0;--i) if(G2.fa[i][x]&&v2[G2.fa[i][x]]<=val) x=G2.fa[i][x];
return x;
}
void build_sm()
{
s1.init();
sort(sm+1,sm+1+cnt);
int x,y,z,tot=n;
for(int i=1;i<=cnt;++i)
{
x=sm[i].x,y=sm[i].y,z=min(sm[i].x,sm[i].y);
x=s1.find(x),y=s1.find(y);
if(x!=y)
{
++tot;
G1.add(tot,x);
G1.add(tot,y);
s1.p[x]=s1.p[y]=tot,v1[tot]=z;
}
}
G1.dfs(tot);
}
void build_bi()
{
b1.init();
sort(bi+1,bi+1+cnt);
int x,y,z,tot=n;
for(int i=1;i<=cnt;++i)
{
x=bi[i].x,y=bi[i].y,z=max(bi[i].x,bi[i].y);
x=b1.find(x),y=b1.find(y);
if(x!=y)
{
++tot;
G2.add(tot,x);
G2.add(tot,y);
b1.p[x]=b1.p[y]=tot,v2[tot]=z;
}
}
M=tot;
G2.dfs(tot);
se.build(rt[0],1,tot);
for(int i=1;i<=tot;++i)
{
if(G2.bin[i]<=n)
rt[i]=se.update(rt[i-1],1,tot,G1.st[G2.bin[i]],1);
else rt[i]=rt[i-1];
}
}
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd()
{
int x=0; char c;
while(c<48) c=nc();
while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc();
return x;
}
int main()
{
// setIO("input");
int x,y,z,s,t,l,r;
n=rd(),m=rd(),Q=rd();
for(int i=1;i<=m;++i)
{
x=rd()+1,y=rd()+1,++cnt;
sm[cnt]=SMA(x,y),bi[cnt]=BIG(x,y);
}
build_sm();
build_bi();
for(int i=1;i<=Q;++i)
{
s=rd()+1,t=rd()+1;
l=rd()+1,r=rd()+1;
// 去：[l,n]
// 回：[1,r]
x=get_sm(s,l); // G1
y=get_bi(t,r); // G2
int L=G1.st[x],R=G1.ed[x];
int r1=G2.ed[y],r2=G2.st[y]-1;
if(se.query(rt[r2],rt[r1],1,M,L,R)) printf("1
");
else printf("0
");
}
return 0;
}