P11065 【MX-X4-T5】「Jason-1」占领高地

原题链接：。

有一张 $n$ 行 $m$ 列的地图，其第 $i$ 行 $j$ 列的位置的**高度**为 $h_{i,j}$ 且**军事化程度**为 $p_{i,j}$，且满足**任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。 （两个位置 $(a, b)$、$(c, d)$ 四连通相邻，当且仅当 $\lvert a - c\rvert + \lvert b - d\rvert = 1$。） 你可以选择若干个位置建立补给站。若在位置 $(i,j)$ 建立了补给站，定义其**运输范围**为所有满足 $h_{i,j} - h_{x,y} + p_{i,j} \geq \lvert i - x\rvert + \lvert j - y\rvert$ 的位置 $(x, y)$。每个补给站都可以在其运输范围中任意移动物资的位置。 定义若干个补给站 $(x, y)$ 的安全程度为其中 $h_{x,y}$ 的最小值。 有 $q$ 次询问，每次给出四个整数 $a, b, c, d$，询问：若要建立若干个补给站，以将物资从位置 $(a, b)$ 运输至位置 $(c, d)$，则建立补给站的安全程度最大值是多少？或报告不可能完成运输任务。 **注意：物资可以通过多个补给站间接运输。不一定必须在 $(a, b)$ 和 $(c, d)$ 两点建立补给站。** **本题数据保证 $\bm{p_{i, j} \le 9}$。**

无

无

**【样例解释 #1】** 第一个询问可以在 $(1,3)$ 建立补给站，安全程度为 $3$。 第二个询问可以在 $(4,1)$ 建立补给站，安全程度为 $4$。 第三个询问可以在 $(3,2)$ 建立补给站，安全程度为 $3$。 第四个询问可以在 $(3,2)$ 建立补给站，安全程度为 $3$。 第五个询问可以在 $(4,1)$ 建立补给站，安全程度为 $4$。 第六个询问可以在 $(4,1),(1,3)$ 建立补给站，安全程度为 $3$。 **【样例解释 #2】** 仅有在 $(1,1)$ 建立的补给站可以将物资在 $(1,1)$、$(1,2)$ 间任意移动，在其它位置建立的补给站都将无法移动任何物资。 故仅有询问 $1$ 可以达成目标，只需在 $(1,1)$ 建立补给站，安全程度为 $1$。 **【数据范围】** **本题采用捆绑测试。** | 子任务 | $q \le$ | $n,m \le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $20$ | $10$ | A | $23$ | | 2 | $10^5$ | $300$ | B | $19$ | | 3 | $10^5$ | $100$ | 无 | $27$ | | 4 | $2 \times 10^5$ | $300$ | 无 | $31$ | - 特殊性质 A：$p_{i, j} \le 4$。 - 特殊性质 B：$p_{i, j} = 0$。 对于 $100 \%$ 的数据，$1 \le n,m \le 300$，$0 \le h_{i,j} \le 10^9$，$\bm{0 \le p_{i,j} \le 9}$，$1 \le q \le 2 \times 10^5$，$1 \le a,c \le n$，$1 \le b,d \le m$，$(a,b) \neq (c,d)$，**保证任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。