Description

官方 PDF 题面

Idea

相当于询问是否存在一个中间点 $X$,满足 $S_i$ 能仅经过编号 $≥ L_i$ 的点走到 $X$,且 $E_i$ 能仅经过编号 $≤ R_i$ 的点走到 $X$。

考虑第一部分,第二部分类似。把边权设置成 $min(A_i, B_i)$,然后求一个 Kruskal 重构树。即模拟 Kruskal 求最小生成树的过程,每次加入一条边时,就新建一个表示这条边的节点,作为那两个点的父亲。

于是 $S_i$ 仅经过编号 $≥ L_i$ 的点能到达的所有点就都在某个子树中——从 $S_i$ 往上倍增找到最浅的 $≥ L_i$ 的那个点的子树。

$E_i$ 那部分同理。

下面询问是否存在一个点同时在两棵子树内,主席树查询 DFS 序即可。

Code