潍坊智能建站模板,百度seo网站优化服务,郴州招聘网,海南建设局网站https://www.luogu.com.cn/problem/P4899
首先#xff0c;我们肯定要建两棵Kruskal重构树的#xff0c;然后判两棵子树是否有相同编号节点
这是个经典问题#xff0c;我们首先可以拍成dfs序#xff0c;然后映射过去#xff0c;然后相当于是判断一个区间是否有 [ l , r …https://www.luogu.com.cn/problem/P4899
首先我们肯定要建两棵Kruskal重构树的然后判两棵子树是否有相同编号节点
这是个经典问题我们首先可以拍成dfs序然后映射过去然后相当于是判断一个区间是否有 [ l , r ] [l,r] [l,r] 内的数直接主席树即可。 #includebits/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 x0,f1;char chgetchar();
while(ch0||ch9){if(ch-)f-1;
chgetchar();}while(ch0ch9){x(x1)
(x3)(ch^48);chgetchar();}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; vectorintG1[N], G2[N]; struct Node {int i, j, k, tot; int F[N], f[N][21], dfn[N], L[N], R[N]; vectorintG[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); }pairint, 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;
}
