「CSP-S 2022」星战 - 图论 + Hash

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

在这一轮的星际战争中，我方在宇宙中建立了 \(n\) 个据点，以 \(m\) 个单向虫洞连接。我们把终点为据点 \(u\) 的所有虫洞归为据点 \(u\) 的虫洞。

战火纷飞之中这些虫洞很难长久存在，敌人的打击随时可能到来。这些打击中的有效打击可以分为两类：

  1. 敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。
  2. 敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

注意：摧毁只会导致虫洞不可用，而不会消除它的存在。

为了抗击敌人并维护各部队和各据点之间的联系，我方发展出了两种特种部队负责修复虫洞：

  • A 型特种部队则可以将某个特定的虫洞修复。
  • B 型特种部队可以将某据点的所有损坏的虫洞修复。

考虑到敌人打击的特点，我方并未在据点上储备过多的战略物资。因此只要这个据点的某一条虫洞被修复，处于可用状态，那么这个据点也是可用的。

我方掌握了一种苛刻的空间特性，利用这一特性我方战舰可以沿着虫洞瞬移到敌方阵营，实现精确打击。

为了把握发动反攻的最佳时机，指挥部必须关注战场上的所有变化，为了寻找一个能够进行反攻的时刻。总指挥认为：

  • 如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。
  • 为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。
  • 如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

总司令为你下达命令，要求你根据战场上实时反馈的信息，迅速告诉他当前的时刻是否能够进行一次反攻。

对于所有数据保证：\(1 \le n \le 5 \times {10}^5\)，\(1 \le m \le 5 \times {10}^5\)，\(1 \le q \le 5 \times {10}^5\)。

解题思路

本题实质是有一张有向图，有若干次加边删边操作，问每次操作完后从每个点出发均可进入一个强连通分量，且每个点的出度为 \(1\)。

由图论知识可推出，只要每个点的出度为 \(1\)，则从任意点出发必定可进入一个强连通分量。因为只要有 \(2\) 点则必有环，只要出现另外的点，由于出度为 \(1\) 则必定连向环或连向连向环的点。于是只要判断出每个点的出度为 \(1\) 则说明该图满足条件。

由于数据范围过大，我们肯定需要在小于 \(O(n)\) 的情况下判断这张图是否满足情况。这时我们可以用 Hash 解决。设每个点对应一个 Hash 值 \(a_i\)（\(a_i\) 可使用随机数生成，且需要是大数以减少冲突概率）和出度 \(d_i\)，我们可以定义这张图的 Hash 值 \(\text{res}\) 为 \(\sum_{i = 1}^n{a_i d_i}\)。只要满足 \(\text{res} = \sum_{i = 1}^n{a_i}\) 即可说明这张图满足条件。对于加边 \(u \rightarrow v\) 操作，我们只需更新 \(\text{res} = \text{res} + a_u\) 即可；同理对于删边 \(u \rightarrow v\) 操作，我们只需更新 \(\text{res} = \text{res} - a_u\) 即可。这样就可实现 \(O(1)\) 处理，\(O(1)\) 查询。

同时我们也需要实现对于据点的加边和删边操作。我们可以对每个点再开一个 Hash 值 \(\text{in}_i\)，表示删除 \(i\) 号点对 \(\text{res}\) 的变化值。每次进行加边和删边操作时，同时在 \(\text{in}_i\) 中操作。即进行加边 \(u \rightarrow v\) 时，更新 \(\text{in}_v = \text{in}_v + a_u\)，进行删边 \(u \rightarrow v\) 时，更新 \(\text{in}_v = \text{in}_v - a_u\)。这样即可在删除 \(v\) 点时，直接更新 \(\text{res} = \text{res} - \text{in}_u\) 并将 \(\text{in}_u\) 清空即可。对于加点操作，我们可以直接在询问前处理出 \(\text{init}_i\) 表示 \(\text{in}_i\) 的最初状态，然后加点时直接恢复至最初状态，即更新 \(\text{res} = \text{res} + \text{init}_i - \text{in}_i\)，\(\text{in}_i = \text{init}_i\) 即可。时间复杂度为 \(O(n)\)

代码演示

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
#include <cstdio>
#include <vector>
#include <random>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    std::vector<unsigned long long> a(n + 1);
    unsigned long long target = 0;

    std::mt19937 rng(std::random_device{}());
    for (int i = 1; i <= n; i++) {
        a[i] = ((unsigned long long)rng() << 31) ^ rng();
        target += a[i];
    }

    std::vector<unsigned long long> init(n + 1);
    unsigned long long res = 0;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        init[v] += a[u];
        res += a[u];
    }

    std::vector<unsigned long long> in(init);

    int q;
    scanf("%d", &q);
    while (q--) {
        int op;
        scanf("%d", &op);

        if (op == 1) {
            int u, v;
            scanf("%d %d", &u, &v);
            in[v] -= a[u];
            res -= a[u];
        } else if (op == 2) {
            int u;
            scanf("%d", &u);
            res -= in[u];
            in[u] = 0;
        } else if (op == 3) {
            int u, v;
            scanf("%d %d", &u, &v);
            in[v] += a[u];
            res += a[u];
        } else if (op == 4) {
            int u;
            scanf("%d", &u);
            res += init[u] - in[u];
            in[u] = init[u];
        }

        if (res == target) puts("YES");
        else puts("NO");
    }

    return 0;
}