题解：P13540 [IOI 2025] 羊驼的坎坷之旅（obstacles）

比较答辩但是很人类的做法！！

注意到起点终点都在第一行，这个看上去很有性质。我们猜测路径一定形如一堆 $(0,a)\to(x,a)\to(x,b)\to(0,b)$。设一列中第一个空的位置是 $fi_i$，前缀连续空的长度是 $cn_i$，$a\to b$ 之间的 $\max H$ 位置为 $c$，那能这么走就相当于 $fi_c\le\min(cn_a,cn_b)$。

这启发我们建出 $H$ 的笛卡尔树。如果我们现在在一个子树 $x$，如果我们能到达 $fi_x$，那去子树内 $cn$ 最大的点肯定是不劣的，然后如果 $\max cn\ge fi_{fa_x}$ 那就可以走到 $x$ 的父亲，询问的时候只要看能跳到最高的位置是否相等即可。倍增做就可以获得 $83$ 分。

对于最后一个 subtask，我们考虑区间笛卡尔树：先一直倍增到子树包含了端点，此时当前节点 $x$ 一定是 $[l,x]$ 或者 $[x,r]$ 的 $\max$。如果两者都是那 $x$ 就是根；如果 $x$ 是 $[l,x]$ 的 $\max$ 那父亲一定是 $R_x=\min\limits_{y>x}H_y>H_x$，左儿子是 $[l,x-1]$，右儿子就是在笛卡尔树上的右儿子。如果右儿子的 $\max cn$ 已经满足要求那直接跳就行，否则需要 $l \le\max\limits_{i<x,cn_i\ge fi_{R_x}}i$，倍增跳 $R$ 的时候维护所有点这个 $\max i$ 的 $\min$ 即可。$x$ 是 $[x,r]$ 的 $\max$ 的情况就是反过来。

时间复杂度 $O(n+m\log nm+q\log m)$。code