三人编程锦标赛 Triinformathlon 题解

wangsiyuan2022 · 2026-05-09 10:01:43 · 题解

solution

很好的题目。

题目让我们解决一个偏序问题，我们可以按照题目要求建边，即如果 a 优于 b，那么建边 a \to b。显然这是一个竞赛图（完全图定向之后的图），我们回答询问的时候，其实就是看 a_i,b_i 之间的可达性。

这个问题看起来不太好解决，那么给出一个定理：竞赛图进行缩点之后，是一条链。

::::success[证明] 考虑归纳法。

起点：n=1 时，只有一个点，可以看作一条链。

归纳：我们有一个 n-1 个点的竞赛图，它缩点之后是一条链，那么我们新加入一个点 n，有以下几种情况。

• 被并入之前的 scc 中，显然不改变缩点之后的图，故成立。
• 前面 n-1 个点都向 n 建边，就是在链尾加上点 n，故成立。
• 否则一定可以找到链中间一个位置，把点 n 插入进去。

::::

接下来我们直接按照题目的优于的判断条件为 cmp 排序（从前到后越来越优），这样我们发现，形成 scc 的部分没有办法正常排序，而 scc 之间的大小关系是正确的，换句话说，就是 scc 在排序后序列的一个区间中。

类似于 tarjan 中的返祖边，在排序后的数组中，如果存在 j < i 并且 j 优于 i，那么 i,j 在一个 scc 中。

• 这个过程可以从后往前扫，然后用线段树判断是否存在优于 i 的位置，实际上是用线段树维护二维偏序存在性，然后搭配扫描线。

• 当然这也可以直接上 cdq，维护出存在 j \to i, j < i 的最小的 j。

最后回答询问的时候条件就是排序后 i,j 的位置 rk_i, rk_j，rk_i < rk_j 或者 rk_i,rk_j 在同一个 scc 中。