Description：

一个无向连通图，多次询问是否存在一条从 $s$ 到 $t$ 的路径从 $s$ 到 $k\geqslant l$ ， $k$ 到 $t\leqslant r$ 。

$1\leqslant n\leqslant 200000$

Solution：

点的 $Kruskal$ 重构树，就是按顺序每次加入一个点，把他和已经加入的但是不在一个联通块里的连起来，这样从 $k$ 出发只经过满足某一条件的点就是这个树的一个子树，于是就变成了判断两组数中是否存在相同的，可以把两个的 $dfs$ 序分别求出来，然后按第二个 $dfs$ 序建主席树，把这个点在第一个 $dfs$ 序的位置插进去，询问的时候就看这个区间和是否大于零即可，其实就是二维数点。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,q;

#define MAXN 400010

vector<int> g[MAXN];

void add(int a,int b)

{

	g[a].push_back(b);g[b].push_back(a);

	return;

}

struct Tree

{

	int root;

	int fa[MAXN];

	int find(int x){return (x == fa[x] ? x : fa[x] = find(fa[x]));}

	struct edge

	{

		int to,nxt;

	}e[MAXN << 1];

	int edgenum;

	int lin[MAXN];

	int rnk[MAXN],siz[MAXN],th[MAXN],tot;

	Tree(){edgenum = tot = 0;memset(lin,0,sizeof(lin));}

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

		return;

	}

	bool vis[MAXN];

	void insert(int k)

	{

	    vis[k] = true;

		for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

		{

		    if(!vis[*i])continue;

			int v = find(*i);

			if(v != k)

			{

				add(k,v);

				fa[v] = k;

			} 

		}

		return;

	}

	int f[MAXN][20];

	void dfs(int k)

	{

		rnk[k] = ++tot;th[tot] = k;

		siz[k] = 1;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(siz[e[i].to] != 0)continue;

			dfs(e[i].to);

			siz[k] += siz[e[i].to];

			f[e[i].to][0] = k;

		}

	}

	void build()

	{

		dfs(root);

		for(int k = 1;k <= 19;++k)

			for(int i = 1;i <= n;++i)

				f[i][k] = f[f[i][k - 1]][k - 1];

		return;

	}

}t1,t2;

struct node

{

	int lc,rc;

	int sum;

	node(){sum = 0;}

}t[MAXN * 30];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void insert(int &rt,int p,int l,int r)

{

	int k = newnode();t[k] = t[rt];rt = k;

	++t[rt].sum;

	if(l == r)return;

	if(p <= mid)insert(t[rt].lc,p,l,mid);

	else insert(t[rt].rc,p,mid + 1,r);

	return; 

}

int query(int rtr,int rtl,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rtr].sum - t[rtl].sum;

	int res = 0;

	if(L <= mid)res += query(t[rtr].lc,t[rtl].lc,L,R,l,mid);

	if(R > mid)res += query(t[rtr].rc,t[rtl].rc,L,R,mid + 1,r);

	return res;

}

int calc2(int p,int v)

{

    for(int i = 19;i >= 0;--i)

        if(t2.f[p][i] != 0 && t2.f[p][i] >= v)

            p = t2.f[p][i];

    return p;

}

int calc1(int p,int v)

{

    for(int i = 19;i >= 0;--i)

        if(t1.f[p][i] != 0 && t1.f[p][i] <= v)

            p = t1.f[p][i];

    return p;

}

bool check(int s,int t,int l,int r)

{

    s = calc2(s,l);

    int sl = t2.rnk[s],sr = t2.rnk[s] + t2.siz[s] - 1;

    t = calc1(t,r);

    int tl = t1.rnk[t],tr = t1.rnk[t] + t1.siz[t] - 1;

    return (query(root[sr],root[sl - 1],tl,tr,1,n) > 0);

}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= m;++i)add(rd() + 1,rd() + 1);

	for(int i = 1;i <= n;++i)t1.fa[i] = t2.fa[i] = i;

	for(int i = 1;i <= n;++i)t1.insert(i);

	for(int i = n;i >= 1;--i)t2.insert(i);

	t1.root = n;

	t2.root = 1;

	t1.build();t2.build();

	int s,t,l,r;

	build(root[0],1,n);

	for(int i = 1;i <= n;++i)

	{

		root[i] = root[i - 1];

		insert(root[i],t1.rnk[t2.th[i]],1,n);

	}

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d%d%d",&s,&t,&l,&r);

		++s;++t;++l;++r;

		if(s < l || t > r)

		{

		    puts("0");

		    continue;

		}

		if(check(s,t,l,r))puts("1");

		else puts("0");

	}

	return 0;

}