憨憨题。
我们发现,狼人形态可以走的点一定是一段前缀,人形可以走的点一定是一段后缀。而且如果需要有解,那就要满足人形状态下从起点出发能走到的点和狼人状态下从终点出发能走到的点一定有交。
因为这个能走到哪些点的限制不太常规,我们可以很容易的把他转换成边权的限制(狼人图和人形图的边权分别取和),这样我们的问题就转换成了:狼人从终点开始再狼人图上走,不能经过权值大于,能走到哪些点。人形同理。然后看看能走到的点有没有交即可。
最小/最大边权能走到哪些点,显然就是个Kruskal重构树中的一个子树。所以我们需要统计两棵不同树的子树内有没有同标号的节点。直接二位数点即可。
/*
_|_| _| _| _|
_| _| _| _|_| _|_|_|_| _| _| _|
_| _| _|_| _| _| _|_|
_| _| _| _| _| _| _| _|
_|_| _| _|_|_|_| _|_| _| _|
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
//#define ls (rt<<1)
//#define rs (rt<<1|1)
#define vi vector<int>
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;i++)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int maxn=2*2e5+100;
int n,m,q;
struct kruskal{
int fa[maxn],cnt,w[maxn],rt,ava,f[maxn][20];
vi son[maxn];
kruskal(){rep(i,0,maxn-1)fa[i]=i;ava=0;}
int get(int x){return (fa[x]==x)?x:(fa[x]=get(fa[x]));}
void uni(int x,int y,int val){
x=get(x),y=get(y);cnt++;fa[x]=cnt,fa[y]=cnt;
son[cnt].pb(x);son[cnt].pb(y);w[cnt]=val;
// cout<<"New Virtual Point Established. Root:"<<cnt<<" Val is"<<val<<endl;
// cout<<"To: "<<x<<' '<<y<<endl;
}
struct gg{
int u,v,w;
}ori[maxn];
static bool cmp1(gg a,gg b){return a.w<b.w;}
static bool cmp2(gg a,gg b){return a.w>b.w;}
void ins(int idx,int u,int v,int w){
ori[idx]=(gg){u,v,w};
}
int l[maxn],r[maxn],size[maxn];
void dfs(int u,int fa){
f[u][0]=fa;rep(i,1,19)f[u][i]=f[f[u][i-1]][i-1];
if(!son[u].size()){
l[u]=r[u]=++ava;size[u]=1;return;
}
l[u]=ava+1;
rep(i,0,(int)(son[u].size())-1){int v=son[u][i];
// cout<<u<<" ---> "<<v<<" val of father is:"<<w[u]<<endl;
dfs(v,u);size[u]+=size[v];
}
r[u]=l[u]+size[u]-1;
// cout<<"Node is: "<<u<<" Segment Get: "<<l[u]<<' '<<r[u]<<endl;
}
void build(){
cnt=n;
// cout<<"Kruskal Tree Init. Listing..."<<endl;
rep(i,1,m){
int u=ori[i].u,v=ori[i].v,val=ori[i].w;
// cout<<u<<' '<<v<<' '<<val<<endl;
if(get(u)!=get(v))uni(u,v,val);
}
rt=cnt;
// cout<<"Kruskal Tree Built. Listing..."<<endl;
dfs(rt,0);
}
pii get_lim(int u,int lim,int ty){
if(!ty){
for(int i=19;i>=0;i--)if(f[u][i]&&w[f[u][i]]<=lim)u=f[u][i];
}
else{
for(int i=19;i>=0;i--)if(f[u][i]&&w[f[u][i]]>=lim)u=f[u][i];
}
return mk(l[u],r[u]);
}
}wolf,human;//wolf 边权越小越好
int ans[maxn];
struct query{
int x,ly,ry,ty,idx;
};
vector<query>qu;
vector<pii> point;
int out[maxn];
bool cmp(query a,query b){return a.x<b.x;}
struct BIT{
int c[maxn];
void add(int loc,int val){for(int i=loc;i<maxn;i+=i&-i)c[i]+=val;}
int query(int loc){int res=0;for(int i=loc;i;i-=i&-i)res+=c[i];return res;}
int seg(int l,int r){return query(r)-query(l-1);}
}t;
int main(){
ios::sync_with_stdio(0);
cin>>n>>m>>q;
rep(i,1,m){
int u,v;cin>>u>>v;u++;v++;
wolf.ins(i,u,v,max(u,v));
human.ins(i,u,v,min(u,v));
}
sort(wolf.ori+1,wolf.ori+1+m,wolf.cmp1);
sort(human.ori+1,human.ori+1+m,human.cmp2);
wolf.build();human.build();
rep(i,1,n){
point.pb(mk(wolf.l[i],human.l[i]));
// cout<<"New Point: ("<<wolf.l[i]<<","<<human.l[i]<<")"<<endl;;
}
rep(i,1,q){
int s,e,l,r;
cin>>s>>e>>l>>r;s++,e++,l++,r++;
pii lima=wolf.get_lim(e,r,0);//0:边权不能大于r wolf的限制控制主区间 (x轴)
pii limb=human.get_lim(s,l,1);//1:边权不能小于l
// cout<<"New Query: ["<<lima.fi<<","<<lima.se<<"] ["<<limb.fi<<","<<limb.se<<"]"<<endl;
qu.pb((query){lima.se,limb.fi,limb.se,1,i});
if(lima.fi>1)qu.pb((query){lima.fi-1,limb.fi,limb.se,-1,i});
}
sort(point.begin(),point.end());
sort(qu.begin(),qu.end(),cmp);
int pptr=0,qptr=0;
rep(i,1,n){
while(pptr<point.size()&&point[pptr].fi==i)t.add(point[pptr].se,1),pptr++;
while(qptr<qu.size()&&qu[qptr].x==i){
out[qu[qptr].idx]+=qu[qptr].ty*t.seg(qu[qptr].ly,qu[qptr].ry);
qptr++;
}
}
rep(i,1,q){
cout<<(bool)(out[i])<<endl;
}
return 0;
}