solution

很好的题目。

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

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

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

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

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

• 被并入之前的 scc 中，显然不改变缩点之后的图，故成立。
• 前面 $n-1$ 个点都向 $n$ 建边，就是在链尾加上点 $n$，故成立。
• $n$ 向前面 $n-1$ 个点建边，就是在链头加上点 $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 中。