题目描述

难度分:$2000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$之和$\leq 2 \times 10^5$，$q$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 2 \times 10^5)$，表示一个$n$ 点$m$边的无向图。节点编号从$1$开始。保证图中无自环和重边。

然后输入长为$n$的数组$h(1 \leq h[i] \leq 10^9)$。每个节点有一座山，第$i$座山的高度为$h[i]$。

然后输入$m$条边。

然后输入$q(1 \leq q \leq 2 \times 10^5)$和$q$个询问，每个询问输入$a$、$b$、$e(0 \leq e \leq 10^9)$。

从第$i$座山移动到和$i$相邻的第$j$座山，你的能量会减少$h[j]-h[i]$。如果这个值是负数则你会增加能量。

只有在移动后能量$\geq 0$的情况下才能从$i$移动到$j$。对于每个询问，回答：在你初始能量为$e$ 的情况下，能否从第$a$座山移动到第$b$座山？输出YES或NO。注意节点编号从$1$开始。

输入样例$1$

2
7 7
1 5 3 4 2 4 1
1 4
4 3
3 6
3 2
2 5
5 6
5 7
5
1 1 3
6 2 0
4 7 0
1 7 4
1 7 2
6 5
4 7 6 2 5 1
1 3
5 3
1 5
2 4
6 2
5
1 5 1
1 3 1
1 2 1000
6 2 6
6 2 5

输出样例$1$

YES
NO
YES
YES
NO

YES
NO
NO
YES
NO

输入样例$2$

2
3 2
1 3 9
1 2
2 3
5
1 1 1
3 2 2
1 1 2
3 3 0
1 2 1
3 3
1 4 1
1 2
2 3
1 3
5
3 3 9
1 3 6
1 1 2
3 3 6
3 3 4

输出样例$2$

YES
YES
YES
YES
NO

YES
YES
YES
YES
YES

输入样例$3$

1
6 10
7 9 2 10 8 6
4 2
6 1
4 5
3 5
6 4
1 3
2 6
6 5
1 2
3 6
5
4 4 8
3 3 1
5 5 9
2 1 7
6 6 10

输出样例$3$

YES
YES
YES
YES
YES

算法

离线+并查集

这个题直接瞪眼还是没什么思路的，但是稍微动动笔就豁然开朗了。假设初始能量为$e$，现在要从$0$到$k$，途中会依次经过$0,1,2,…,k-1,k$这些节点，则必须满足：

$e-(h_1-h_0) \geq 0$
$e-(h_1-h_0)-(h_2-h_1) \geq 0$
$e-(h_1-h_0)-(h_2-h_1)-(h_3-h_2) \geq 0$
……
$e-(h_1-h_0)-(h_2-h_1)-(h_3-h_2)…-(h_k-h_{k-1}) \geq 0$

相互抵消后发现只需要$e+h_0 \geq h_i$（$i \in [1,k]$）就可以了。因此我们可以先将所有边$(u,v)$按照$max(h[u],h[v])$排序，所有询问按照$e+h[a]$排序，按照这个顺序考虑每个询问，对于某个询问$i$的阈值$threshold=e_i+h[a_i]$，把边集中$max(h[u],h[v])$不超过$threshold$的节点$u$、$v$都加入到图中，用并查集维护连通性（合并$u$和$v$）。然后遍历属于这个阈值的所有询问，看看$a_i$和$b_i$是不是连通的。

遍历更大的$threshold$时，其实小阈值的边集已经全部被加入到图中了，因此指向边集的指针并不会回退。这样一来跑一遍双指针算法就能求得所有答案，最后再把答案按照询问顺序输出就可以了。

复杂度分析

时间复杂度

对边集和询问排序的时间复杂度为$O(mlog_2n)$和$O(qlog_2q)$，然后双指针算法求答案的时间复杂度为$O((m+q)log_2n)$，其中$log_2n$是对并查集执行合并操作时的大约时间复杂度。因此，整个算法的时间复杂度为$O(mlog_2m+qlog_2q+(m+q)log_2n)$。

空间复杂度

除了输入的$h$数组，并查集的空间复杂度为$O(n)$，边数组的空间复杂度为$O(m)$，答案数组$ans$的空间复杂度为$O(q)$。因此，整个算法的额外空间复杂度为$O(n+m+q)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
int T, n, m, q, h[N], p[N];
bool ans[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
    }
}

bool is_connected(int x, int y) {
    return find(x) == find(y);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &h[i]);
            p[i] = i;
        }
        vector<array<int, 3>> edges;
        for(int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            edges.push_back({max(h[u], h[v]), u, v});
        }
        sort(edges.begin(), edges.end());
        scanf("%d", &q);
        map<int, vector<array<int, 3>>> queries;
        for(int i = 1; i <= q; i++) {
            ans[i] = false;
            int a, b, e;
            scanf("%d%d%d", &a, &b, &e);
            queries[h[a] + e].push_back({a, b, i});
        }
        int j = 0;
        for(auto&[threshold, qs]: queries) {
            while(j < m && edges[j][0] <= threshold) {
                int u = edges[j][1], v = edges[j][2];
                merge(u, v);
                j++;
            }
            for(auto&query: qs) {
                int a = query[0], b = query[1], index = query[2];
                ans[index] = is_connected(a, b);
            }
        }
        for(int i = 1; i <= q; i++) {
            if(ans[i]) {
                puts("YES");
            }else {
                puts("NO");
            }
        }
        puts("");
    }
    return 0;
}