题解：P13540 [IOI 2025] Obstacles for a Llama

题外话：我做出来了？我做出来了？我做出来了？中国队只过了一个人的题我做出来了？？？

其实我觉得 $83\rightarrow 100$ 非常简单啊。

我们考虑这个东西简直就是双序列拓展。回忆一下这个题的题意，就是一样的网格，问你能不能从左上走到右下。做这个题的时候我就回忆了一下双序列拓展的几个做法，用热门做法做这个题好像是死路一条，后来想起来我补题的第一个做法是这个，突然就大有思路！

我们先考虑 $l=0,r=m-1$ 的特殊性质。

首先一句转化就是两个点不可达当且仅当存在一个割，也就是一条不合法的从中间穿过去的路径。可以得到如下几种形式的割（显然要从两个点中间出发；以及忽略对称的情况）：

注意此处上面的不一定都是直线，只是表达可达性。

我们给左右两边和下面都加一层不可达的点，这样前两种都可以归为第三种（走边路回到第一行）。假设我们能预处理处每一对点 $(i,j)$ 之间是否可以形成割，那两个点 $(s,d)$ 是连通的当且仅当对于任意有割的 $(i,j)$ 都满足，$[i<s<j]=[i<d<j]$。这里容易想到 xor hashing，我们给每一对 $(i,j)$ 赋随机权值，给区间里的异或随机权值，这样就是判断两个点的权值是否相同。

考虑 $(i,j)$ 之间的割。上面说了不一定是直线。但是真的不一定是直线吗？手玩一下可以证明，如果一条路径从 $(0,i)$ 出发到 $(0,j)$ 结束，那必然存在一个 $k$ 使得 $(0,i)$ 到 $(k,i)$ 到 $(k,j)$ 到 $(0,j)$ 的三条直线段都是不合法点。说人话就是那个圈是三条直线。

举一个手玩的例子。称最后的三条线和顶边形成了一个“矩形”。如下图，如果在右下角折了一下，那固定矩形左上角不变，右下角一定可以是折线右下角小矩形四个点之一，否则不合法点之间不满足行列互相包含。对于其它情况，如凸凹状，也可以类似反证。当然严谨证明我还是不会的。

还有一个观察是如果取出了一个矩形，中间有一列也是全部不合法的，那这个矩形可以选择不要，因为中间一列把它分成了两个小矩形，可以代替它。

所以我们可以限制找的 $(i,j)$ 必须满足 $\max(b_{i+1,\dots,j-1})<\min(b_i,b_j)$，否则中间更大的这一列比两边更容易不合法。那很容易看出来这样的 $(i,j)$ 只有 $O(n)$ 对了。具体来说就是 $i$ 是 $j$ 左边第一个 $b_i\ge b_j$ 的或者相反一定符合一个。

枚举 $(i,j)$，然后需要问是否存在一个 $k$ 使得 $\min(b_i,b_j)\ge \max_{l=0}^k a_l$ 以及 $\min_{t=i}^j b_t\ge a_k$。对于第一个限制，$l$ 是一段前缀，可以二分出来。然后对于第二个限制，求一下前缀内的最优 $a_k$ 即可。

这样特殊性质就做完了，时间复杂度 $O(n+m\log m+q)$。代码。

然后你考虑加上 $[l,r]$ 的限制，那这就等价于我们在两边加的边框收缩了。首先本来就不可达的肯定还是不可达。现在其实只加了一个限制，相当于最开始三种割的第二个（从两个点之间到了两边）。这个同理是两段直线，我们枚举割的起点，很容易二分求出这个横着的直线最远到哪里。然后回答询问的时候 rmq 求出中间最长的横线即可。时间复杂度 $O(n+m\log m+q)$。

笑点解析是我懒得写 rmq 交上去 $O(mq)$ 的时候直接通过了后三个包（ioi 赛制拼包情况下就是直接过了），提交记录。

通过代码。