题意回顾

• 有向图，$n$ 个点，每个点至少一条出边
• 初始只有 $A$ 点为黑色，其余白色
• 游戏过程：
  • Alice 选一个编号 $\leq k$ 的黑点 $u$
  • Bob 从 $u$ 的出边中选一个点染黑
• 定义 $(A,B)$ 是好的：如果从 $A$ 开始，Alice 能强制让 $B$ 被染黑（无论 Bob 怎么选）
• 对每个 $k=1..n$，求好的 $(A,B)$ 对数量（$A \neq B$）

数据范围：$n \leq 2\times 10^5$，$\sum l \leq 5\times 10^5$。

关键结论

$(A,B)$ 是好的当且仅当在只保留编号 $\leq k$ 的点的子图 $G_k$ 中：

1. 存在 $A$ 到 $B$ 的路径
2. $B$ 所在的强连通分量（SCC）是 $G_k$ 的一个汇点（即在 $G_k$ 的 SCC 分解中，该 SCC 没有出边指向其他 SCC）

算法框架

1. 增量处理

从 $k=1$ 到 $n$ 依次处理，每次加入点 $k$ 及其相关边。

2. 维护 SCC

使用并查集（DSU）维护当前 $G_k$ 的强连通分量。

3. 动态维护汇点 SCC

对每个 SCC 维护：

• 大小 $size$
• 出边集合（指向其他 SCC）
• 标记是否为汇点

4. 统计答案

对每个汇点 SCC，设能到达它的点数为 $R$，则它贡献 $(R - 1) \times size$ 个好对。

算法步骤

初始化

• $ans[k] = 0$
• DSU 初始化，每个点单独成 SCC
• 每个 SCC 的 $outdeg = 0$（出边到其他 SCC 的数量）
• $reachable[SCC] =$ 该 SCC 的大小

处理 $k=1$ 到 $n$

1. 加入点 $k$
2. 对 $k$ 的每条出边 $(k,v)$：
   • 如果 $v \leq k$，在 DAG 中添加边 $(SCC(k), SCC(v))$
   • 如果 $SCC(k) \neq SCC(v)$，则增加 $SCC(k)$ 的出度
3. 检查并合并形成环的 SCC
4. 更新汇点 SCC 集合
5. 对每个汇点 SCC 计算 $R$ = 能到达它的点数
6. $ans[k] = \sum_{S \in \text{sinks}} (R_S - 1) \times size_S$

复杂度分析

• 使用路径压缩 + 按秩合并的 DSU：$O(m \alpha(n))$
• 动态维护 SCC 出度和可达性：$O(m \log n)$
• 总复杂度：$O((n+m) \log n)$，可过 $n \leq 2\times 10^5$

总结

本题的核心在于将博弈条件转化为图论中的汇点 SCC 可达性问题，通过增量加点和动态维护 SCC 来高效求解所有 $k$ 的答案。