[IOI2018] werewolf 狼人（Kruskal重构树 + 主席树）

https://www.luogu.com.cn/problem/P4899

首先，我们肯定要建两棵Kruskal重构树的，然后判两棵子树是否有相同编号节点

这是个经典问题，我们首先可以拍成dfs序，然后映射过去，然后相当于是判断一个区间是否有 $[l,r]$ 内的数，直接主席树即可。

	#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
int n, m, i, j, k, T;
int q, u, v; 

vector<int>G1[N], G2[N]; 

struct Node {
	int i, j, k, tot; 
	int F[N], f[N][21], dfn[N], L[N], R[N]; 
	vector<int>G[N]; 
	int fa(int x) { 
		if(F[x] == x) return x; 
		return F[x] = fa(F[x]); 
	}
	void set() {
		for(i = 1; i <= n; ++i) F[i] = i; 
	}
	void add(int x, int y) {
		if(x == fa(y)) return ; 
		debug("cun %d %d\n", x, fa(y)); 
		G[x].pb(fa(y)); F[fa(y)] = x; 
	}
	void dfs(int x) {
		dfn[++tot] = x; L[x] = tot;
		for(int y : G[x]) dfs(y), f[y][0] = x; R[x] = tot; 
	}
	void work() {
		for(k = 1; k <= 20; ++k) 
			for(i = 1; i <= n; ++i) f[i][k] = f[f[i][k - 1]][k - 1];
		debug("dfn "); for(i = 1; i <= n; ++i) debug("%d ", dfn[i]); debug("\n"); 
	}
	pair<int, int> jump(int x, int lim, int op) {
		for(k = 20; k >= 0; --k)
			if(f[x][k]) {
				if(op == 0 && f[x][k] < lim) continue; 
				if(op == 1 && f[x][k] > lim) continue; 
				x = f[x][k]; 
			}
		return {L[x], R[x]}; 
	}
}T1, T2;

int tot, s[N << 5], ls[N << 5], rs[N << 5]; 

struct Segment_tree {
#define mid ((l + r) >> 1)
	void add(int &k, int u, int l, int r, int x) {
		if(!k) k = ++tot; 
		if(l == r) return ++s[k], void(); 
		if(x <= mid) add(ls[k], ls[u], l, mid, x); 
		else add(rs[k], rs[u], mid + 1, r, x); 
		if(!ls[k]) ls[k] = ls[u]; if(!rs[k]) rs[k] = rs[u]; 
		s[k] = s[ls[k]] + s[rs[k]]; 
	}
	int qry(int k, int l, int r, int x, int y) {
		if(l >= x && r <= y) return s[k]; 
		int sum = 0; 
		if(x <= mid) sum += qry(ls[k], l, mid, x, y); 
		if(y >= mid + 1) sum += qry(rs[k], mid + 1, r, x, y); 
		return sum; 
	}
}Seg; 
int rt[N]; 

int a[N], b[N]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); m = read(); q = read(); 
	for(i = 1; i <= m; ++i) {
		u = read() + 1; v = read() + 1; if(u > v) swap(u, v); 
		debug("%d %d\n", u, v); 
		G1[u].pb(v); G2[v].pb(u); 
	}
	T1.set(); T2.set(); 
	for(i = 1; i <= n; ++i) 
		for(int j : G2[i]) T1.add(i, j); 
	for(i = n; i >= 1; --i) 
		for(int j : G1[i]) T2.add(i, j); 
	T1.dfs(n); T2.dfs(1); T1.work(); T2.work(); 
	for(i = 1; i <= n; ++i) b[T1.dfn[i]] = i; 
	for(i = 1; i <= n; ++i) a[i] = b[T2.dfn[i]]; 
	for(i = 1; i <= n; ++i) debug("%d ", a[i]); debug("\n"); 
	for(i = 1; i <= n; ++i) Seg.add(rt[i], rt[i - 1], 1, n, a[i]); 
	while(q--) {
		int L, R; 
		u = read() + 1; v = read() + 1; L = read() + 1; R = read() + 1; 
		debug("(%d %d) [%d %d]\n", u, v, L, R); 
		if(u < L || v > R) { printf("0\n"); continue; }
		auto t1 = T2.jump(u, L, 0); auto t2 = T1.jump(v, R, 1); 
		int l1 = t1.fi, r1 = t1.se, l2 = t2.fi, r2 = t2.se; 
		debug("[%d %d] [%d %d]\n", l1, r1, l2, r2); 
		int s = Seg.qry(rt[r1], 1, n, l2, r2) - Seg.qry(rt[l1 - 1], 1, n, l2, r2); 
		printf(s ? "1\n" : "0\n"); 
	}
	return 0;
}