小圆亲亲！| 【解题报告】P12768 [POI 2018 #3] 三人编程锦标赛 / Triinformathlon

Starrykiller · 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 内。这可以用数据结构+并查集维护。