[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 LOCALfreopen("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;
}