题目分析

1. 分层图结构

题目给出的特殊条件是：

$$\left\lfloor \frac{b}{k} \right\rfloor = 1 + \left\lfloor \frac{a}{k} \right\rfloor $$

这意味着：

• 所有边都是从某一层连向下一层，不会跨层或回退
• 图是一个有向无环图 (DAG)
• 节点可以按层划分：第 $i$ 层包含节点 $[i \cdot k, (i+1)\cdot k - 1]$（最后一层可能不满）

---

2. 问题转化

对于查询 $(a, b)$：

• 设 $s = \lfloor a/k \rfloor$，$t = \lfloor b/k \rfloor$
• 如果 $t \le s$，则输出 $-1$（因为只能往高层走）
• 否则，路径必须经过层 $s, s+1, \dots, t$，且每步只能到下一层

---

3. 核心思路

用 min-plus 矩阵乘法 表示层间最短路径：

• 定义 $M_i$ 为从层 $i$ 到层 $i+1$ 的 $k \times k$ 最短路径矩阵
• 从层 $p$ 到层 $q$ 的最短路径矩阵为：

$$R = M_p \otimes M_{p+1} \otimes \dots \otimes M_{q-1} $$

其中 $\otimes$ 是 min-plus 矩阵乘法：

$$(A \otimes B)[x][y] = \min_{z} (A[x][z] + B[z][y]) $$

---

4. 倍增预处理

直接对每个查询做矩阵连乘太慢，使用 Sparse Table 预处理：

• $\text{st}[j][i]$ 表示从层 $i$ 到层 $i + 2^j$ 的合并矩阵
• 预处理：

$$\text{st}[0][i] = M_i$$ $$\text{st}[j][i] = \text{st}[j-1][i] \otimes \text{st}[j-1][i + 2^{j-1}] $$

• 查询时，将区间 $[s, t)$ 拆成 $O(\log L)$ 个矩阵相乘

---

5. 复杂度分析

• 层数 $L \le \frac{n}{k} \le 10000$
• $k \le 5$，矩阵乘法 $O(k^3) \le 125$
• 预处理 $O(L \log L \cdot k^3)$ ≈ $1.75 \times 10^7$
• 每个查询 $O(\log L \cdot k^3)$ ≈ $1750$，总 $1.75 \times 10^7$，可接受

---

6. 算法流程

1. 读入数据，构建每层的转移矩阵 $M_i$
2. 用倍增法预处理 ST 表
3. 对于每个查询 $(a,b)$：
   • 计算 $s = \lfloor a/k \rfloor$, $t = \lfloor b/k \rfloor$
   • 如果 $t \le s$，输出 $-1$
   • 否则用 ST 表合并 $[s, t)$ 区间的矩阵
   • 输出矩阵中对应位置的值

---