题解 P5332 【[JSOI2019]精准预测】
Lice
·
·
题解
Description
现有一台预测机，可以预测当前 n 个人在 T 个时刻内的生死关系。关系有两种：
这样的关系共有 m 条。现在你需要在不违背这些关系的前提下，计算对于每一个人 i，可能可以与 i 活到第 T+1 时刻的有多少人。形式化的讲，设 \text{Live}(i, j) 表示是否 i, j 可以同时存活，如果可以则为 1，反之为 0。那么你需要对于每一个 i\in[1, n]，计算
\sum_{j\in[1, n],i\ne j}\text{Live}(i, j)
的值。
Hint
### 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
以下代码部分参考了 [这篇博客](https://blog.csdn.net/qq_39972971/article/details/93032127)。
```cpp
/*
* 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;
}
```