[ABC365F] Takahashi on Grid 题解

zrl123456 · 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)。

代码