可以发现的是，这个问题本质上是在问你能否从一个点 (S) 出发经过不小于 (L) 的所有点再经过不大于 (R) 的点能否到达 (E)。
你会发现但看这两个要求都是一个经典的问题，即都是在 ( m Kruskal) 重构树上的一颗子树。
那么我们可以把这个问题放到 ( m Kruskal) 重构树上来，按照边权从小到大建树。
那么你会发现问题变成首先不能走进若干棵子树后面不能走出如果棵子树的问题，但这是非常复杂的，因此需要考虑简化这个问题。
我们所熟悉的问题是单独考虑一个限制的问题，那么能否将这个问题转化为我们熟悉的经典问题呢？
答案是可以的，不难发现前者是从 (S) 开始在边权从大到小的重构树上的一颗子树，后者是从 (E) 出发边权从小到大的重构树上的一颗子树。
那么考虑将这两棵重构树建立出来，问题就转化为判定来自于两棵树的两个不同子树是否存在交集的问题。
直接整体从两个子树来看待这个问题是不佳的，因此我们可以将这个问题看作是在附加在某一个子树上的限制条件。
那么问题就可以转化成在 (B) 这棵树上的那个子树内，是否存在一个在 (A) 这棵树上哪个子树内的点。
不难发现存于某个子树内最佳的判定方式就是使用 (dfs) 序，于是还可以将问题转化为：
是否存在一个在 (B) 上的那颗子树内的点在 (A) 上的 (dfs) 序在 (A) 上的那颗子树对应的区间。
不难发现可以直接按照 (B) 上每个点在 (A) 上的 (dfs) 序建立一颗权值线段树，问题就变成在某个区间内是否存在一个数的问题了。
至于要查询 (B) 某棵子树的权值线段树，直接主席树/线段树合并即可。
#include <bits/stdc++.h>
using namespace std;
#define ls t[p].l
#define rs t[p].r
#define mid (l + r >> 1)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define dep(i, l, r) for (int i = r; i >= l; --i)
#define Nxt(i, u) for (int i = H[u]; i; i = E[i].next)
#define Next(i, u) for (int i = h[u]; i; i = e[i].next)
const int N = 200000 + 5;
const int M = 20 + 5;
int n, m, q, u, v, s, e, l, r, cnt, tot, H[N], rt[N];
struct Edge { int v, next;} E[N * 4];
struct tree { int sum, l, r;} t[N * M];
struct node { int p, w;} ;
bool cmp(node x, node y) { return x.w < y.w;}
struct Kruskal {
struct edge { int v, next;} e[N << 1];
node a[N];
int tot, cnt, h[N], fa[N], sz[N], dfn[N], inv[N], f[N][M];
int Find(int x) { return x == fa[x] ? fa[x] : fa[x] = Find(fa[x]);}
void add(int u, int v) {
e[++tot].v = v, e[tot].next = h[u], h[u] = tot;
e[++tot].v = u, e[tot].next = h[v], h[v] = tot;
}
void Merge(int x, int y) {
int a = Find(x), b = Find(y);
if(a == b) return;
fa[b] = a, add(a, b);
}
void dfs(int u, int fa) {
dfn[u] = ++cnt, inv[cnt] = u, sz[u] = 1, f[u][0] = fa;
Next(i, u) if(e[i].v != fa) dfs(e[i].v, u), sz[u] += sz[e[i].v];
}
void build(int type) {
rep(i, 1, n) a[i].p = i, a[i].w = i * type;
sort(a + 1, a + n + 1, cmp);
rep(i, 1, n) fa[i] = i;
rep(i, 1, n) {
int u = a[i].p;
Nxt(j, u) {
int v = E[j].v;
if(v * type < u * type) Merge(u, v);
}
}
dfs(a[n].p, 0);
rep(j, 1, 20) rep(i, 1, n) f[i][j] = f[f[i][j - 1]][j - 1];
}
int find(int x, int k, int type) {
dep(i, 0, 20) if(f[x][i] && f[x][i] * type <= k * type) x = f[x][i];
return x;
}
}A, B;
int read() {
char c; int x = 0, f = 1;
c = getchar();
while (c > '9' || c < '0') { if(c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
void build(int &p, int l, int r) {
p = ++cnt; if(l == r) return;
build(ls, l, mid), build(rs, mid + 1, r);
}
void update(int &p, int k, int l, int r, int x, int y) {
p = ++cnt, t[p] = t[k], ++t[p].sum;
if(l == r) return;
if(mid >= x) update(ls, t[k].l, l, mid, x, y);
if(mid < y) update(rs, t[k].r, mid + 1, r, x, y);
}
int query(int p, int k, int l, int r, int x, int y) {
if(!p || l >= x && r <= y) return t[p].sum - t[k].sum;
int ans = 0;
if(mid >= x) ans += query(ls, t[k].l, l, mid, x, y);
if(mid < y) ans += query(rs, t[k].r, mid + 1, r, x, y);
return ans;
}
void add(int u, int v) {
E[++tot].v = v, E[tot].next = H[u], H[u] = tot;
E[++tot].v = u, E[tot].next = H[v], H[v] = tot;
}
int main() {
n = read(), m = read(), q = read();
rep(i, 1, m) u = read() + 1, v = read() + 1, add(u, v);
A.build(-1), B.build(1);
build(rt[0], 1, n);
rep(i, 1, n) update(rt[i], rt[i - 1], 1, n, A.dfn[B.inv[i]], A.dfn[B.inv[i]]);
while (q--) {
s = read() + 1, e = read() + 1, l = read() + 1, r = read() + 1;
int FA = A.find(s, l, -1), FB = B.find(e, r, 1);
printf("%d
", (query(rt[B.dfn[FB] + B.sz[FB] - 1], rt[B.dfn[FB] - 1], 1, n, A.dfn[FA], A.dfn[FA] + A.sz[FA] - 1) > 0));
}
return 0;
}
当问题由多个经典问题组成时，一个好的处理方式是将问题划归成单个经典问题之间的联系。
当需要解决几个事件直接满足的某个条件不好做时，可以尝试从一个事件出发去看待这个条件。