本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-08 13:34:21

[ABC365F] Takahashi on Grid

题目考察：ST 表，倍增。
题目简述：
有一个地图 $a$，横坐标在 $[1,n]$。地图上有一些点可以通过，对于 $i\in[1,n]$，$a_{i,l_i},a_{i,l_{i+1}},\dots,a_{i,t_i}$ 是可以通过的。然后有 $q$ 次询问，每次询问给出 $s_x,s_y,t_x,t_y$，求从 $(s_x,s_y)$ 到 $(t_x,t_y)$ 所走的最短路径。
数据范围：

• $1\le n,q\le 2\times 10^5$
• $\forall i\in[1,n],1\le l_i,u_i\le 10^9$
• $\forall i\in[1,n-1],[l_i,u_i]\cup[l_{i+1},u_{i+1}]\ne\emptyset$
• $1\le s_x,t_x\le n,l_{s_x}\le s_y\le u_{s_x},l_{t_x}\le t_y\le u_{t_x}$

我们将 $x$ 坐标为 $i$ 的所有点称为第 $i$ 层，由于每一层的可通过点都是一个区间。所以说我们用一种贪心策略（能下一层就不继续走），设我们在走到下一层要向左走：

• 若我们的走到下下层要向左走，那么我们一直往左或下走就可以得到最短路。
• 反之，我们肯定希望靠着右边走，这样才能更快的往下走。

那么我们可以维护一个 ST 表，$mx_{i,j}$ 表示 $\displaystyle\max_{k=i}^{i+2^j-1}(l_k)$，$mn_{i,j}$ 表示 $\displaystyle\min_{k=i}^{i+2^j-1}(u_k)$，然后我们倍增对于每一个询问一直往下跳，直到跳不下去了为止。我们在预处理出 $fl_{i,j}$ 和 $fu_{i,j}$，代表从 $l_i$ 和 $u_i$ 跳下去 $2^j-1$ 层所花费的代价，然后我们往下跳 $2^j-1$ 层，花费 $fl_{i,j}$ 或 $fu_{i,j}$（$j$ 是最大的 $j$ 使 $2^j\le len$，这里的 $len$ 指还需要往下跳的层数），继续往下递归（当然我们可以用同样的方法求出 $fl$ 和 $fu$）。
这样我们每次求都是 $\Theta(\log n)$ 的，然后我们求 ST 表都是 $\Theta(n\log n)$ 的，所以总体复杂度是 $\Theta(n\log^2 n+q\log n)$。

代码