一、题目核心理解

迷宫是分层结构：

• 第 $k$ 层 = 所有满足 $\max(x, y) = k$ 的格子。
• 第 $1$ 层：$(1,1)$
• 第 $2$ 层：$(1,2),(2,1),(2,2)$
• 第 $3$ 层：$(1,3),(2,3),(3,1),(3,2),(3,3)$，以此类推。

层与层之间只有两个门：

• 顶部墙的门：在第 $i$ 层的顶部边上，即 $(i, y)$ 且 $y \le i$。
• 右侧墙的门：在第 $i$ 层的右侧边上，即 $(x, i)$ 且 $x \le i$。

---

二、关键观察

1. 同一层内移动：
   层内格子形成一个“L”形或矩形，但实际可走路径是曼哈顿距离，因为同一层内没有墙（墙只在层之间）。

2. 跨层移动：
   只能通过两个门进入下一层（或上一层）。
   进入下一层后，必须立刻在该层内走到该层的另一个门才能继续往下。

3. 最优路径结构：
   从第 $l_1$ 层到第 $l_2$ 层（$l_1 < l_2$）：

   • 先在 $l_1$ 层内走到该层的某个门
   • 进入 $l_1+1$ 层
   • 在 $l_1+1$ 层内走到该层的某个门
   • 继续直到 $l_2$ 层
   • 最后在 $l_2$ 层内走到目标点

---

三、动态规划预处理

定义 $d[i][0]$ = 第 $i$ 层顶部墙上的门坐标，$d[i][1]$ = 第 $i$ 层右侧墙上的门坐标（坐标从 $0$ 开始）。

1. 层间转移代价

从第 $i$ 层到第 $i+1$ 层：

• 如果从 $i$ 层的顶部门 $(d[i][0])$ 出发，进入 $i+1$ 层后，要走到 $i+1$ 层的某个门 $d[i+1][k]$（$k \in \{0,1\}$）：

  • 进入 $i+1$ 层的点：$d[i][0]$ 正上方一格？不对，门在 $i$ 层顶部，进入 $i+1$ 层后位置是 $(i+1, d[i][0].y)$。
  • 因为 $d[i][0] = (i, y_0)$，门在 $(i, y_0)$ 和 $(i+1, y_0)$ 之间。
  • 进入 $i+1$ 层后位于 $(i+1, y_0)$。
  • 然后走到 $d[i+1][k]$ 的距离：
    • 若 $k=0$（顶部门）：$(i+1, y_0)$ → $(i+1, y_{next})$，曼哈顿距离 = $|y_0 - y_{next}|$，然后要进入下一层？不对，这里是走到 $i+1$ 层的门，还没跨层。
    • 实际上代码中是：

      abs(d[i][0].x + 1 - d[i+1][k].x) + abs(d[i][0].y - d[i+1][k].y) + 1
      

      因为 $d[i][0].x = i$（0-based），加 1 后为 $i+1$，所以 $|(i+1) - d[i+1][k].x| + |d[i][0].y - d[i+1][k].y|$ 是层内距离，$+1$ 是穿过门的那一步。

• 如果从 $i$ 层的右侧门 $(d[i][1] = (x_0, i))$ 出发，进入 $i+1$ 层后位于 $(x_0, i+1)$：

  abs(d[i][1].x - d[i+1][k].x) + abs(d[i][1].y + 1 - d[i+1][k].y) + 1
  

所以定义：

• $dp[i][0][0][k]$ = 从第 $i$ 层顶部门到第 $i+1$ 层第 $k$ 个门的最小步数。
• $dp[i][0][1][k]$ = 从第 $i$ 层右侧门到第 $i+1$ 层第 $k$ 个门的最小步数。

但代码中 $dp[i][0][j][k]$ 的 $i$ 是从 $0$ 到 $n-3$，表示从第 i+1 层到第 i+2 层？要仔细看。

其实索引：

• 有 $n-1$ 层门的信息（第 1 到 n-1 层的门）。
• 层间转移：从第 $i$ 层（$i$ 从 1 到 n-2）到第 $i+1$ 层，需要 $d[i]$ 和 $d[i+1]$。

所以 $dp[i][0][j][k]$ 表示从第 $i+1$ 层的门 $j$ 到第 $i+2$ 层的门 $k$ 的最小代价？不对，看下标：

代码中：

forn(i, n-2) forn(k,2){
    dp[i][0][0][k] = abs(d[i][0].x+1 - d[i+1][k].x) + abs(d[i][0].y - d[i+1][k].y) + 1;
    dp[i][0][1][k] = abs(d[i][1].x - d[i+1][k].x) + abs(d[i][1].y+1 - d[i+1][k].y) + 1;
}

这里 $d[i]$ 和 $d[i+1]$ 的索引：$i$ 从 0 到 n-3，$d[i]$ 和 $d[i+1]$ 都存在（因为 $d$ 长度 $n-1$）。

所以 $dp[i][l][j][k]$ 表示：从第 $i+1$ 层的门 $j$ 到第 $i+1+2^l$ 层的门 $k$ 的最小步数。

---

四、倍增优化

用倍增（binary lifting）合并区间：

dp[i][l][j][k] = min over t ( dp[i][l-1][j][t] + dp[i + (1<<(l-1))][l-1][t][k] )

这样可以在 $O(\log n)$ 时间内从第 $l_1$ 层跳到第 $l_2$ 层。

---

五、查询处理

对于询问 $(x_1,y_1) \to (x_2,y_2)$：

1. 计算所在层 $l_1 = \max(x_1,y_1)$，$l_2 = \max(x_2,y_2)$，若 $l_1 > l_2$ 则交换。
2. 若同层：直接曼哈顿距离。
3. 否则：
   • 从起点走到第 $l_1$ 层的两个门的代价：

     ndp[0] = |x1 - d[l1][0].x| + |y1 - d[l1][0].y|
     ndp[1] = |x1 - d[l1][1].x| + |y1 - d[l1][1].y|
     

     注意这里 $d[l1][0]$ 是第 $l_1$ 层的门坐标（0-based），起点坐标也是 0-based。
   • 用倍增从 $l_1$ 跳到 $l_2-1$（因为最后要进入 $l_2$ 层），每次合并 $ndp$：

     tmp[k] = min(ndp[j] + dp[l1][i][j][k])
     

   • 最后从 $l_2-1$ 层的门走到终点：

     ans = min(
       ndp[0] + |d[l1][0].x+1 - x2| + |d[l1][0].y - y2| + 1,
       ndp[1] + |d[l1][1].x - x2| + |d[l1][1].y+1 - y2| + 1
     )
     

     这里 $l_1$ 经过倍增后已经变成 $l_2-1$。

---

六、复杂度

• 预处理：$O(n \log n \cdot 8)$
• 每个查询：$O(\log n)$

总复杂度 $O((n+m) \log n)$，可以通过 $n=10^5, m=2\times 10^5$。

---

七、代码对应关系

• $d[i][0]$：第 $i+1$ 层顶部门的坐标
• $d[i][1]$：第 $i+1$ 层右侧门的坐标
• $dp[i][l][j][k]$：从第 $i+1$ 层门 $j$ 到第 $i+2^l+1$ 层门 $k$ 的最小步数
• $ndp[0], ndp[1]$：当前所在层的两个门的累计代价

---

八、核心公式

层内曼哈顿距离：

$$\text{dist}((x_1,y_1),(x_2,y_2)) = |x_1-x_2| + |y_1-y_2| $$

跨层代价（从第 $i$ 层顶部门到第 $i+1$ 层门 $k$）：

$$|(i+1) - d[i+1][k].x| + |d[i][0].y - d[i+1][k].y| + 1 $$

跨层代价（从第 $i$ 层右侧门到第 $i+1$ 层门 $k$）：

$$|d[i][1].x - d[i+1][k].x| + |(i+1) - d[i+1][k].y| + 1 $$

倍增合并：

$$dp[i][l][j][k] = \min_{t \in \{0,1\}} \left( dp[i][l-1][j][t] + dp[i+2^{l-1}][l-1][t][k] \right) $$

查询答案：

$$\min\left( \begin{aligned} &ndp[0] + |d[l_2-1][0].x+1 - x_2| + |d[l_2-1][0].y - y_2| + 1, \\ &ndp[1] + |d[l_2-1][1].x - x_2| + |d[l_2-1][1].y+1 - y_2| + 1 \end{aligned} \right) $$

---