洛谷P8819 [CSP-S 2022] 星战题解

题目链接：P8819 [CSP-S 2022] 星战

题意：

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

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

敌人会摧毁某个虫洞，这会使它连接的两个据点无法再通过这个虫洞直接到达，但这样的打击无法摧毁它连接的两个据点。

敌人会摧毁某个据点，由于虫洞的主要技术集中在出口处，这会导致该据点的所有还未被摧毁的虫洞被一同摧毁。而从这个据点出发的虫洞则不会摧毁。

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

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

A 型特种部队则可以将某个特定的虫洞修复。

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

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

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

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

如果从我方的任何据点出发，在选择了合适的路线的前提下，可以进行无限次的虫洞穿梭（可以多次经过同一据点或同一虫洞），那么这个据点就可以实现反击。

为了使虫洞穿梭的过程连续，尽量减少战舰在据点切换虫洞时的质能损耗，当且仅当只有一个从该据点出发的虫洞可用时，这个据点可以实现连续穿梭。

如果我方所有据点都可以实现反击，也都可以实现连续穿梭，那么这个时刻就是一个绝佳的反攻时刻。

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

输入格式：

输入的第一行包含两个正整数 \(n,m\)。

接下来 \(m\) 行每行两个数 \(u,v\)，表示一个从据点 \(u\) 出发到据点 \(v\) 的虫洞。保证 \(u \ne v\)，保证不会有两条相同的虫洞。初始时所有的虫洞和据点都是完好的。

接下来一行一个正整数 \(q\) 表示询问个数。

接下来 \(q\) 行每行表示一次询问或操作。首先读入一个正整数 \(t\) 表示指令类型：

若 \(t = 1\)，接下来两个整数 \(u, v\) 表示敌人摧毁了从据点 \(u\) 出发到据点 \(v\) 的虫洞。保证该虫洞存在且未被摧毁。

若 \(t = 2\)，接下来一个整数 \(u\) 表示敌人摧毁了据点 \(u\)。如果该据点的虫洞已全部被摧毁，那么这次袭击不会有任何效果。

若 \(t = 3\)，接下来两个整数 \(u, v\) 表示我方修复了从据点 \(u\) 出发到据点 \(v\) 的虫洞。保证该虫洞存在且被摧毁。

若 \(t = 4\)，接下来一个整数 \(u\) 表示我方修复了据点 \(u\)。如果该据点没有被摧毁的虫洞，那么这次修复不会有任何效果。

在每次指令执行之后，你需要判断能否进行一次反攻。如果能则输出 YES 否则输出 NO。

输出格式：

输出一共 \(q\) 行。对于每个指令，输出这个指令执行后能否进行反攻。

数据范围：

\(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\) 时，可以反攻。

直接暴力统计的复杂度是 \(\mathcal{O}(nq)\) 的，考虑给每个点随机赋权 \(w(u)\) （这种做法叫和哈希(sum hash)）

记 \(r(v)=\sum_{(u,v) \in E} w(u)\) ，即所有入边的点的哈希，并记 \(\operatorname{deg}(u)\) 为 \(u\) 的出度

那么显然有 \[ \sum_v r(v) = \sum_u \operatorname{deg}(u) \cdot w(u)\tag{1} \] 同时，显然可以证明 \[ \sum_v r(v) = \sum_u w(u)\tag{2} \] 是所有点出度为 \(1\) 的一个必要条件。

那么 \((2)\) 是否充分呢？我们把 \(\operatorname{deg}(u)\) 看作未知量，则 \((1,1,\cdots,1)\) 显然是一组合法解

除此以外，确实可能存在合法解。但是其他解即使存在，恰好满足的概率也不高，因为 \(w(u)\) 是随机的。

因此我们可以认为这个必要不充分条件，在很大概率下是充分的。

如果你觉得不放心可以多赋几个权值，即 \(w_i(u)\) 为第 \(i\) 组的哈希值

显然两组权值出现重复合法解的概率非常低，不行就三组（大雾），但是本题其实一组就够了。

时间复杂度 \(\mathcal{O}(k(n + m))\) ，\(k\) 为设定的哈希组数

代码：（就写了一组哈希）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

mt19937 rd(time(0));
int sum, now, w[N], r[N], mx[N];
void solve()
{
    int x, u, v; cin >> x;
    switch(x)
    {
        case 1:
            cin >> u >> v; r[v] -= w[u]; now -= w[u];
            break;
        case 2:
            cin >> v; now -= r[v]; r[v] = 0;
            break;
        case 3:
            cin >> u >> v; r[v] += w[u]; now += w[u];
            break;
        case 4:
            cin >> v; now += mx[v] - r[v]; r[v] = mx[v];
            break;
        default: 
            cerr << "WRONG INPUT" << '\n';
            break;
    }
    cout << (now == sum ? "YES" : "NO") << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) { w[i] = rd(); sum += w[i]; }
    for(int i = 1, u, v; i <= m; i++)
    {
        cin >> u >> v;
        r[v] += w[u]; mx[v] = r[v]; now += w[u];
    }
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}