题目链接

题目大意

给出一个 $n$ 个点 $m$ 条边的无向联通图，有 $q$ 组询问，每组询问给出 $x,~y,~l,~r$，询问是否存在一个点 $p$ 满足：

1. 存在一条从 $x$ 到 $p$ 的路径满足路径上所有节点（包含两个端点）编号均不小于 $l$。
2. 存在一条从 $p$ 到 $y$ 的路径满足路径上所有节点（包含两个端点）编号均不大于 $r$。

$n,~q \le 2 \times 10^5,~m \le 4 \times 10^5$

分析

由于对 $x \to p$ 和 $p \to y$ 的路径的限制均为“均不小于 $x$”或“均不大于 $x$”的形式，我们考虑使用 Kruskal 重构树解决这一问题。因为当我们将每条边的边权设为其两端端点的较大值时重构树上两点的 LCA 的权值即为这两点在原图上点权最大值最小的路径所对应的路径点权最大值。维护最大的路径最小值的方法同理。

由于我们无法同时满足这两个限制，因此我们考虑建两棵 Kruskal 重构树，第一棵维护路径上最大的最小值，第二棵维护路径上最小的最大值。对于一组询问，考虑合法的 $p$ 可能在什么位置：

1. $p$ 在第一棵树上位于 $x$ 的深度最小的满足 $\ge l$ 的祖先 $fx$ 的子树中。
2. $p$ 在第二棵树上位于 $y$ 的深度最小的满足 $\le r$ 的祖先 $fy$ 的子树中。

考虑在两棵树上分别求出所有节点的 dfs 序 dfn[0/1][i]，对于节点 $i$ 将其视为坐标系上一个位于 $(dfn[0][i],~dfn[1][i])$ 的点。则每个询问等同于询问坐标系上一个矩形内是否存在点。将所有询问离线后二维数点即可。

代码

View on GitHub

/**
 * @author Macesuted (i@macesuted.moe)
 * @copyright Copyright (c) 2021
 * @brief
 *      My Solution: https://macesuted.moe/article/lg4899
 */

#include <bits/stdc++.h>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c <= '9' && c >= '0'; c = getchar())
        x = x * 10 + (c & 15);
    return x * f;
}

#define maxn 200005
#define maxlgn 20

typedef pair<int, int> pii;

class KruscalTree {
   private:
    int f[maxn];
    bool vis[maxn];

    int getfa(int p) { return f[p] == p ? p : f[p] = getfa(f[p]); }

   public:
    vector<vector<int>> tree;
    int fa[maxn][maxlgn], dfni[maxn], dfno[maxn], tim = 0;
    void dfs(int p, int pre) {
        dfni[p] = ++tim;
        fa[p][0] = pre;
        for (int i = 1; i < maxlgn; i++) fa[p][i] = fa[fa[p][i - 1]][i - 1];
        for (auto i : tree[p]) dfs(i, p);
        dfno[p] = tim;
        return;
    }
    void build(int n, const vector<vector<int>>& graph, int p[]) {
        for (int i = 1; i <= n; i++) vis[i] = false, f[i] = i;
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            vis[p[i]] = true;
            for (auto j : graph[p[i]])
                if (vis[j] && getfa(p[i]) != getfa(j))
                    tree[p[i]].push_back(getfa(j)), f[getfa(j)] = p[i];
        }
        return dfs(p[n], p[n]);
    }
} T[2];
class BIT {
   private:
    int tree[maxn];

   public:
    void add(int p, int v) {
        for (int i = p; i < maxn; i += i & -i) tree[i] += v;
        return;
    }
    int sum(int p) {
        int sum = 0;
        for (int i = p; i; i -= i & -i) sum += tree[i];
        return sum;
    }
} bit;

struct Ask {
    int l, r, id, op;
};

int p[maxn];

vector<vector<int>> graph;
vector<Ask> asks[maxn];
int points[maxn];
int answer[maxn];

int main() {
    ios::sync_with_stdio(false);
    cout << setiosflags(ios::fixed) << setprecision(8);
    int n = read<int>(), m = read<int>(), q = read<int>();
    graph.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int x = read<int>() + 1, y = read<int>() + 1;
        graph[x].push_back(y), graph[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) p[i] = n - i + 1;
    T[0].build(n, graph, p), reverse(p + 1, p + n + 1), T[1].build(n, graph, p);
    for (int i = 1; i <= n; i++) points[T[0].dfni[i]] = T[1].dfni[i];
    for (int i = 1; i <= q; i++) {
        int S = read<int>() + 1, E = read<int>() + 1, l = read<int>() + 1, r = read<int>() + 1;
        for (int i = maxlgn - 1; ~i; i--)
            if (T[0].fa[S][i] >= l) S = T[0].fa[S][i];
        for (int i = maxlgn - 1; ~i; i--)
            if (T[1].fa[E][i] <= r) E = T[1].fa[E][i];
        if (T[0].dfni[S] - 1) asks[T[0].dfni[S] - 1].push_back({T[1].dfni[E], T[1].dfno[E], i, -1});
        asks[T[0].dfno[S]].push_back({T[1].dfni[E], T[1].dfno[E], i, +1});
    }
    for (int i = 1; i <= n; i++) {
        bit.add(points[i], +1);
        for (auto j : asks[i]) answer[j.id] += j.op * (bit.sum(j.r) - bit.sum(j.l - 1));
    }
    for (int i = 1; i <= q; i++) cout << (answer[i] >= 1) << endl;
    return 0;
}