题解 P4899 【[IOI2018] werewolf 狼人】
GKxx
2019-03-30 23:34:57
从$S$出发，只经过编号大于等于$L$的点，能够到达的所有点构成的集合记为$A$；
从$E$出发，只经过编号小于等于$R$的点，能够到达的所有点构成的集合记为$B$，
那么就是要求$A\cap B$是否为空集。
自然想到kruskal重构树，先对每条边以两个端点的编号较小值为权值生成最大生成树对应的重构树$TS$，再对每条边以端点编号较大值为权值生成最小生成树对应的重构树$TE$
那么在$TS$上倍增地往上跳，找到结点$x$，满足：以$x$为根的子树中的所有叶节点（也就对应到原图中的结点）编号都大于等于$L$，并且$x$是深度尽可能小的那个点。在$TE$上也倍增往上跳，找到$y$，满足：以$y$为根的子树中的所有叶节点编号都小于等于$R$，并且$y$是深度尽可能小的那个点。
那么$TS$中以$x$为根的子树的所有叶节点就构成了集合$A$，$TE$中以$y$为根的子树的所有叶节点就构成了集合$B$，现在要求它们的交集。考虑求出两棵树的dfs序，于是就变成了两个序列，每次给出两个区间，求交集。[带修改版：CF1093E](https://www.luogu.org/problemnew/show/CF1093E)。上数据结构维护就行了。可以离线树状数组，但是我这种懒人当然是用主席树了
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T &x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T &x, const T &y) { return y < x ? x = y, 1 : 0; }
template <typename T> inline bool chkmax(T &x, const T &y) { return x < y ? x = y, 1 : 0; }
const int maxn = 2e5 + 207, maxm = 4e5 + 207, inf = INT_MAX;
struct Edge {
int x, y;
Edge(int a, int b) : x(a), y(b) {}
Edge() : x(0), y(0) {}
};
Edge e[maxm];
int n, m, q;
struct Tree {
int v[maxm], head[maxm], next[maxm], value[maxm], tot;
int dfn[maxm], st[maxm], ed[maxm], fa[30][maxm], xys;
void add_edge(int x, int y) {
v[++tot] = y;
next[tot] = head[x];
head[x] = tot;
}
void dfs(int x) {
if (x <= n) {
dfn[++xys] = x, value[x] = x;
st[x] = xys;
} else st[x] = xys + 1;
for (int i = 1; i <= 20; ++i)
fa[i][x] = fa[i - 1][fa[i - 1][x]];
for (int i = head[x]; i; i = next[i]) {
fa[0][v[i]] = x;
dfs(v[i]);
}
ed[x] = xys;
}
int find_s(int x, int ll) {
for (int i = 20; ~i; --i)
if (value[fa[i][x]] >= ll) x = fa[i][x];
return x;
}
int find_e(int x, int rr) {
for (int i = 20; ~i; --i)
if (value[fa[i][x]] <= rr) x = fa[i][x];
return x;
}
};
Tree TS, TE;
inline bool cmpmin(const Edge &a, const Edge &b) {
return std::min(a.x, a.y) > std::min(b.x, b.y);
}
inline bool cmpmax(const Edge &a, const Edge &b) {
return std::max(a.x, a.y) < std::max(b.x, b.y);
}
struct Ufs {
int fa[maxm];
void init(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
int findf(int x) { return fa[x] == x ? x : fa[x] = findf(fa[x]); }
};
inline void kruskal(Tree &T, int tp) {
if (tp == 1) std::sort(e + 1, e + m + 1, cmpmin);
else std::sort(e + 1, e + m + 1, cmpmax);
int node = n;
Ufs ufs;
ufs.init(n << 1);
for (int i = 1; i <= m; ++i) {
int x = e[i].x, y = e[i].y;
int w = tp == 1 ? std::min(x, y) : std::max(x, y);
if ((x = ufs.findf(x)) != (y = ufs.findf(y))) {
ufs.fa[x] = ufs.fa[y] = ++node;
T.value[node] = w;
T.add_edge(node, x);
T.add_edge(node, y);
}
}
T.dfs(node);
}
struct Ctree_node {
int lc, rc, s;
Ctree_node() : lc(0), rc(0), s(0) {}
};
int p[maxn];
struct Chairman_tree {
Ctree_node T[maxn << 5];
int root[maxn], tot;
void insert(int &o, int l, int r, int pos, int val) {
T[++tot] = T[o]; T[o = tot].s += val;
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) insert(T[o].lc, l, mid, pos, val);
else insert(T[o].rc, mid + 1, r, pos, val);
}
int query(int lt, int rt, int lb, int rb, int l, int r) {
if (!(lt || rt) || l > rb || r < lb) return 0;
if (l <= lb && r >= rb) return T[rt].s - T[lt].s;
int mid = (lb + rb) >> 1;
return query(T[lt].lc, T[rt].lc, lb, mid, l, r) + query(T[lt].rc, T[rt].rc, mid + 1, rb, l, r);
}
};
Chairman_tree ct;
int main() {
read(n, m, q);
for (int i = 1; i <= m; ++i) {
read(e[i].x, e[i].y);
++e[i].x; ++e[i].y;
}
kruskal(TS, 1);
kruskal(TE, 2);
TE.value[0] = inf;
for (int i = 1; i <= n; ++i) p[TS.dfn[i]] = i;
ct.root[0] = 0;
for (int i = 1; i <= n; ++i) {
ct.root[i] = ct.root[i - 1];
ct.insert(ct.root[i], 1, n, p[TE.dfn[i]], 1);
}
for (int i = 1; i <= q; ++i) {
int s, e, ll, rr;
read(s, e, ll, rr);
++s; ++e; ++ll; ++rr;
int x = TS.find_s(s, ll);
int y = TE.find_e(e, rr);
int res = ct.query(ct.root[TE.st[y] - 1], ct.root[TE.ed[y]], 1, n, TS.st[x], TS.ed[x]);
puts(res ? "1" : "0");
}
return 0;
}
```