DDOSvoid's Blog

2022杭电多校3 J Range Reachability Query

发表于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7171

简要题意：给定一个 $n$ 个点 $m$ 条边的 $DAG$，现在有 $q$ 次询问，每次询问给定 $u,v,l,r$，问从 $u$ 出发，只经过编号在 $[l,r]$ 内的边能否到达 $v$

$n,q\le 50000,m\le 100000$

Solution

注意询问为 $DAG$ 可达性，显然只能使用 $bitset$，另外每个询问都固定了一个区间内的边，我们考虑离线

令 $S_i$ 表示有第 $i$ 条边的询问集合，同时我们令 $f_{u,i}$ 从 $u$ 出发，只经过 $[l_i,r_i]$ 内的边能否到达 $v_i$，这个东西我们拿 $bitset$ 优化，然后拓扑排序后，我们按照逆序更新 $f$ 即可，具体的，对于第 $k$ 条边 $(u,v)$，$f_u=f_u~or~(f_v~and~S_k)$，至于如何求 $S_k$，我们将询问离线后扫描线即可，但是由于空间限制，所以我们 $S_k$ 需要使用分组 $bitset$ 来存储

时间复杂度 $O(\frac{qm}{w}+Bm)$，$B$ 取 $5$ 即可满足空间限制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <queue>
#define maxn 50010
#define maxm 100010
#define maxq 50010
#define sqtn 25010
using namespace std;

int n, m, q;

const int N = 50000;
bitset<N + 1> f[maxn], B[sqtn];

vector<pair<int, int>> G[maxn]; int in[maxn];

struct Query {
    int opt, k, x;
} Q[maxq * 2]; int cnt;
int qq[maxq];

int l[sqtn], r[sqtn], bl[maxq * 2], blo, num, id[maxm];
void init_blo(int n) {
    blo = min(n, 5); num = (n + blo - 1) / blo;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1; 
    for (int i = 1; i <= num; ++i) {
        l[i] = (i - 1) * blo + 1;
        r[i] = i * blo;
    } r[num] = n;

    sort(Q + 1, Q + n + 1, [](const Query &u, const Query &v) { return u.k < v.k; });
    for (int i = 1; i <= num; ++i) {
        B[i] = B[i - 1]; 
        for (int j = l[i]; j <= r[i]; ++j) 
            B[i].set(Q[j].x, Q[j].opt);
    }
}

bitset<N + 1> get(int x) {
    int Bl = bl[x]; bitset<N + 1> bits = B[Bl - 1];
    for (int i = l[Bl]; i <= x; ++i) bits.set(Q[i].x, Q[i].opt);
    return bits;
}

int tp[maxn];
void topsort() {
    queue<int> Q; int cnt = 0; 
    for (int i = 1; i <= n; ++i)
        if (!in[i]) Q.push(i);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); tp[++cnt] = u;
        for (auto [v, id] : G[u])
            if (--in[v] == 0) Q.push(v);
    }
}

void work() {
    cin >> n >> m >> q; 
    for (int i = 1; i <= n; ++i) f[i].reset(); cnt = 0; 
    for (int i = 1; i <= n; ++i) G[i].clear(), in[i] = 0; 
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        G[x].emplace_back(y, i); ++in[y];
    } 
    for (int i = 1; i <= q; ++i) {
        int x, y, l, r; cin >> x >> y >> l >> r;
        qq[i] = x;
        Q[++cnt] = { 1, l, i };
        Q[++cnt] = { 0, r + 1, i };
        f[y].set(i);
    } init_blo(cnt);
    for (int i = 1, j = 1; i <= m; ++i) { 
        while (j <= cnt && Q[j].k <= i) ++j;
        id[i] = j - 1; 
    } topsort(); reverse(tp + 1, tp + n + 1);
    for (int i = 1, u = tp[i]; i <= n; u = tp[++i]) 
        for (auto [v, k] : G[u])
            if (id[k]) f[u] |= f[v] & get(id[k]);
    for (int i = 1; i <= q; ++i) cout << (f[qq[i]][i] ? "YES" : "NO") << "\n";
}

int main() { freopen("1010.in", "r", stdin); freopen("1010.ans", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}