[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;
}

原文地址：https://blog.csdn.net/zhangtingxiqwq/article/details/142915172

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！