题解：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 赛制拼包情况下就是直接过了），提交记录。

通过代码。