自动搬运

查看原文

来自洛谷，原作者为

	Lice 这个人懒散惯了，什么都没写

搬运于2025-08-24 22:09:39，当前版本为作者最后更新于2020-10-20 19:24:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Description

现有一台预测机，可以预测当前 $n$ 个人在 $T$ 个时刻内的生死关系。关系有两种：

• $\texttt{0 t x y}$：如果 $t$ 时刻 $x$ 死了，那么 $y$ 在第 $t+1$ 时刻也会死亡。
• $\texttt{1 t x y}$：如果 $t$ 时刻 $x$ 活着，那么 $y$ 在 $t$ 时刻就会死亡。

这样的关系共有 $m$ 条。现在你需要在不违背这些关系的前提下，计算对于每一个人 $i$，可能可以与 $i$ 活到第 $T+1$ 时刻的有多少人。形式化的讲，设 $\text{Live}(i, j)$ 表示是否 $i, j$ 可以同时存活，如果可以则为 $1$，反之为 $0$。那么你需要对于每一个 $i\in[1, n]$，计算

的值。

Hint

$1\le n\le 5\times 10^4, 1\le m\le 10^5, 1\le T\le 10^6$。

Solution

考虑用 2-SAT 思想将生死关系转化为图：记 $(x,t), \neg (x,t)$ 分别表示 $x$ 这个人在时刻 $t$ 的 活 / 死 两个状态（图上的顶点），$a\to b$ 表示一条从 $a$ 到 $b$ 的有向边。

• 对于一个人 $i$，如果 $t$ 时刻他死了，那么显然 $t+1$ 时刻也是死的。同理，如果 $t+1$ 时刻是活的，那么 $t$ 时刻一定也是活的。连边 $\neg(i, t)\to \neg(i,t+1),(i,t+1)\to(i,t)$。
• 对于一个关系 $\texttt{0 t x y}$，显然连边 $\neg(x, t)\to \neg(y,t+1)$。注意如果 $t+1$ 时 $y$ 没死，那么说明这个条件没有生效，在 $t$ 时刻 $x$ 是活的，所以 $(y,t+1)\to (x,t)$。
• 对于一个关系 $\texttt{1 t x y}$，显然连边 $(x, t)\to \neg(y,t)$。同上反向考虑有 $(y, t)\to \neg(x,t)$。

这样我们就把图建好了。然而我们发现 闷声发大财 点数是 $O(n\times T)$ 的。其实这个还好办，我们只要对每个点 $x$，把它在条件中出现过的 $t$ 作为点开出来，其他 没有出现在条件中的就是没用的点。具体来讲，对每个点开一个 set 存储有用的时刻（包括 $T+1$），然后用一个 map 存一下编号即可。这样一来，点和边的规模为 $O(m+n)$，可以承受。

那么，如何用这张图求解答案呢？为了方便，设 $\text{alive}(x) = (x, T+1),\text{dead}(x) = \neg(x, T+1)$，分别表示最后结束时 $x$ 这个人生死对应的两个状态。

我们考虑一条有向边 $a\to b$ 的实际意义：如果 $a$ 为真，那么可以推出 $b$ 也为真。如果说存在一个 $y\ne x$ 使得 $\text{alive}(x)$ 可以到达 $\text{dead}(y)$，那么表明 $x$ 活着的话 $y$ 就会死，这样两个人显然无法同时活着。

如果我们对于每个 $x$ 都求出满足上述条件的 $y$ 集合的大小，那么 $n$ 减去这个集合的大小再减一（减去自己）即为答案。

在实际实现时，我们枚举 $i\in [1, n]$ 并从 $\text{alive}(i)$ 开始 DFS，搜出这个 $\text{alive}(i)$ 可以搜到那些 $\text{dead}(j)$，最后我们得到了一个由所有 $\text{alive}(i)$ 可及的 $\text{dead}(j)$ 组成的一个集合，然后答案就比较显然了。

但这样的复杂度是平方级别，我们考虑优化。发现对于 DFS 树上的一个结点 $x$ 以及其子节点 $y_1, y_2, \cdots y_k$。若记 $f(i)$ 为 $i$ 可以到达的点集，那么 $f(x) = \left(\cup_{i=1}^k f(y_i)\right)\cup\{x\}$。不难发现这个 $\cup$ 其实是可以用 bitset 的位运算 进行优化的，复杂度降为 $O(\frac 1 \omega n(n+m))$。注意，这里 $f$ 也有记忆化的作用，使得一个点不被搜两次。既然是记忆化，那么相当于在 DAG 上 dp。具体为什么是 DAG，发现只会有生 $\to$ 死的边而没有死 $\to$ 生的，并且死 $\to$ 死的边存在时间先后顺序，不会存在 SCC。

难受的是 $\frac 1 \omega n(n+m)$ 大小的 bitset 直接炸空间了，于是我们使用神奇技巧强行卡进去。

考虑把 $n$ 个人分成若干块 分批处理，一块 $B$ 个，然后空间常数就小下来了。实测 $B\approx 2\times 10^4$ 时可过。

实现上一个细节：特别标记 必死点，即 $\text{alive}(x)$ 可以到达 $\text{dead}(x)$。这种点单独输出 $0$。

Code

以下代码部分参考了 这篇博客。

/*
 * Author : _Wallace_
 * Source : https://www.cnblogs.com/-Wallace-/
 * Problem : JSOI2019 精准预测
 */
#include <algorithm>
#include <bitset>
#include <iostream>
#include <set>
#include <map>
#include <vector>

using namespace std;
const int N = 5e4 + 5;
const int MaxT = 1e6 + 5;
const int M = 1e5 + 5;
const int B = 1e4;
const int V = (M + N) << 1;

int n, m, T;
int type[M], t[M], x[M], y[M];
int ans[N];

set<int> vaild[N];
map<int, int> idx[N][2];
int total = 0;

vector<int> adj[V]; // graph
void link(int u, int v) { adj[u].emplace_back(v); }

int l[N], d[N], bel[V]; // live, dead
bitset<N> dead;
bitset<V> vis;
bitset<B> statu[V]; // f

void dfs(int x, int p, int q) {
    if (vis[x]) return; vis.set(x);
    statu[x].reset();
    if (p <= bel[x] && bel[x] <= q) statu[x].set(bel[x] - p);
    for (auto y : adj[x]) dfs(y, p, q), statu[x] |= statu[y];
}

signed main() {
    ios::sync_with_stdio(false), cin >> T >> n >> m;
    for (int i = 1; i <= m; i++) cin >> type[i] >> t[i] >> x[i] >> y[i];
    for (int i = 1; i <= n; i++) vaild[i].insert(T + 1);
    for (int i = 1; i <= m; i++) vaild[x[i]].insert(t[i]);
    for (int i = 1; i <= n; i++) {
        for (auto t : vaild[i])
            idx[i][0][t] = ++total, idx[i][1][t] = ++total;
        for (auto t = vaild[i].begin(); t != vaild[i].end() && next(t) != vaild[i].end(); t++)
            link(idx[i][0][*t], idx[i][0][*next(t)]), link(idx[i][1][*next(t)], idx[i][1][*t]);
    }
    for (int i = 1; i <= m; i++) {
        if (!type[i]) {
            int to = *vaild[y[i]].upper_bound(t[i]);
            link(idx[x[i]][0][t[i]], idx[y[i]][0][to]);
            link(idx[y[i]][1][to], idx[x[i]][1][t[i]]);
        } else {
            int to = *vaild[y[i]].lower_bound(t[i]);
            link(idx[x[i]][1][t[i]], idx[y[i]][0][to]);
            link(idx[y[i]][1][to], idx[x[i]][0][t[i]]);
        }
    }

    for (int i = 1; i <= n; i++) l[i] = idx[i][1][T + 1], bel[d[i] = idx[i][0][T + 1]] = i;
    for (int p = 1, q; p <= n; p += B) {
        q = min(p + B - 1, n), vis.reset();
        for (int i = 1; i <= n; i++) dfs(l[i], p, q);
        bitset<B> cur;
        for (int i = p; i <= q; i++) if (statu[l[i]][i - p]) dead.set(i), cur.set(i - p);
        for (int i = 1; i <= n; i++) ans[i] += (q - p + 1) - (cur | statu[l[i]]).count();
    }
    for (int i = 1; i <= n; i++)
        cout << (dead[i] ? 0 : ans[i] - 1) << ' ';
    return cout << endl, 0;
}