题解 P4899 【[IOI2018] werewolf 狼人】

感觉已经几次碰到这种类型的题目了，写篇$Blog$总结一下 ### 题意： 是否存在一条$(s_i, t_i)$的路径，满足先只走编号超过$L_i$的点，再走编号不超过$R_i$的点 ### $Solution$： 对于这种限定经过点数的题目，可以比较自然地想到重构树： 由于前后都有限定，我们考虑建两颗重构树 第一颗按照边权为两个端点编号的最小值构建重构树，重构树每个点的点权$x$表示不经过边权超过$x$的边能到达的所有点； 第二颗则按照边权为两个端点最大值来构建重构树，重构树上每个点点权$x$表示不经过边权$≤x$的边能到达的所有点。 构建完重构树后，对于每一个$s_i$，只需要在重构树上一直往上跳，找到一个点$x$，满足$L_i≤val_x$即可，$t_i$同理 这样我们会在两颗重构树上找到两个点，现在问题就转化成了：这两个点构成的子树中，有没有公共点（因为有公共点$x$的话就肯定存在一条合法路径为$s_i->x->t_i$） 树上两个节点的交我们不太好做，考虑我们需要的是子树的交，对应在$dfs$序中是一段区间，于是问题就进一步转化： 对于两个排列$a, b$，每次询问排列$a$在$[l_1, r_1]$区间内，排列$b$在$[l_2, r_2]$区间内有无公共元素 ~~其他题解到这一步怎么就是一句： 离线树状数组/在线主席树一下 就没了啊~~ 由于两个数列都是排列，我们可以考律把排列$a$映射到排列$b$中去： 记$gg[i]$表示$i$这个元素在排列$a$中出现的位置，于是我们可以得到一个$gg[b[i]]$的一个新的排列，这个排列的意义为：$b_i$在$a$中的出现位置 所以我们可以考律对$gg[b[i]]$建一棵主席树（离线树状数组也行），每一个询问只需要查询在$[l_2, r_2]$这些版本内，$[l_1, r_1]$有无元素即可 ## $Code:$ ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define drep(i, s, t) for(re int i = t; i >= s; -- i) #define Next(i, u) for(re int i = head[u]; i; i = e[i].next) #define _ 400005 int n, m, fa[_], q, fr[_], to[_], head[_], cnt, gg[_], size[_ * 15], ls[_ * 15], rs[_ * 15], gk, rt[_]; struct Edge { int v, next; }e[_ << 1]; struct edge { int u, v, w; }E[_]; il void add(int u, int v) { e[++ cnt] = (Edge){v, head[u]}, head[u] = cnt; } il bool cmp(edge a, edge b) { return a.w < b.w; } il int find(int x) { while(x != fa[x]) x = fa[x] = fa[fa[x]]; return x; } struct Tree { int L[_], R[_], pax, dfn[_], val[_], f[21][_]; il void dfs(int u) { if(u <= n) L[u] = ++ pax, dfn[pax] = u, val[u] = u; else L[u] = pax + 1; rep(i, 1, 20) f[i][u] = f[i - 1][f[i - 1][u]]; Next(i, u) f[0][e[i].v] = u, dfs(e[i].v); R[u] = pax; } il int find_pre(int x, int y) { drep(i, 0, 20) if(val[f[i][x]] >= y && f[i][x]) x = f[i][x]; return x; } il int find_nxt(int x, int y) { drep(i, 0, 20) if(val[f[i][x]] <= y && f[i][x]) x = f[i][x]; return x; } }t1, t2;//重构树中用倍增找到我们需要的最高点 il void solve(Tree&t, int opt) { rep(i, 1, n * 2) fa[i] = i; int tot = n; rep(i, 1, m) { if(opt == 1) E[i] = (edge){fr[i], to[i], -min(fr[i], to[i])}; if(opt == 2) E[i] = (edge){fr[i], to[i], max(fr[i], to[i])}; } sort(E + 1, E + m + 1, cmp); rep(i, 1, m) { int u = E[i].u, v = E[i].v, a = find(u), b = find(v); if(a != b) fa[a] = fa[b] = ++ tot, t.val[tot] = abs(E[i].w), add(tot, a), add(tot, b); } t.dfs(tot); }//构建重构树 il void insert(int &k, int kk, int l, int r, int ll) { if(!k) k = ++ gk; size[k] = size[kk] + 1; if(l == r) return; int mid = (l + r) >> 1; if(ll <= mid) insert(ls[k], ls[kk], l, mid, ll), rs[k] = rs[kk]; else insert(rs[k], rs[kk], mid + 1, r, ll), ls[k] = ls[kk]; } il int query(int k, int kk, int l, int r, int ll, int rr) { if(ll <= l && r <= rr) return size[kk] - size[k]; int mid = (l + r) >> 1, ans = 0; if(ll <= mid) ans += query(ls[k], ls[kk], l, mid, ll, rr); if(mid < rr) ans += query(rs[k], rs[kk], mid + 1, r, ll, rr); return ans; }//主席树求交 int main() { n = read(), m = read(), q = read(); rep(i, 1, m) fr[i] = read() + 1, to[i] = read() + 1; solve(t1, 1), cnt = 0, memset(head, 0, sizeof(head)), solve(t2, 2); rep(i, 1, n) gg[t1.dfn[i]] = i; rep(i, 1, n) insert(rt[i], rt[i - 1], 1, n, gg[t2.dfn[i]]); while(q --) { int s = read() + 1, t = read() + 1, l = read() + 1, r = read() + 1, x = t1.find_pre(s, l), y = t2.find_nxt(t, r); printf("%d\n", query(rt[t2.L[y] - 1], rt[t2.R[y]], 1, n, t1.L[x], t1.R[x]) > 0); } return 0; } ``` ~~代码就凑合着看吧，我承认它非常丑，把它拆成及部分看的话也不是很难写~~