自动搬运

查看原文

来自洛谷，原作者为

	Starrykiller 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 23:17:59，当前版本为作者最后更新于2025-06-11 15:59:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

定义 $i\gt j\iff i$ 道德上优于 $j$。这显然是一个严格全序。因此，这是一张竞赛图。

我们用 $\texttt{std::sort}$ 对 $1\sim n$ 排序后，设得到的排列为 $p_1\sim p_n$，显然在同一个 SCC 内的元素都在一个区间内。我们只需要将同一个 SCC 内的元素并起来即可。

考虑如何刻画 SCC。对于 $\forall 1\le i\le n$，找到最小的 $1\le j\lt i$ 使得 $p_j\gt p_i$，则 $p_j,p_{j+1},\ldots,p_i$ 在一个 SCC 内。这可以用数据结构+并查集维护。