本文共 706 字，大约阅读时间需要 2 分钟。
为了帮助 FJ 找到最佳位置放置他的玉米田，需要解决多个查询，每个查询要求在一个 B x B 的子矩阵中找到最大和最小的海拔值。为了高效处理这些查询，通常采用二维范围查询（2D RMQ）算法。
代码使用动态规划预处理矩阵，建立三个三维数组 dpmin、dpmax 和 val，分别存储不同块的最小值、最大值和原始值。预处理过程分为几个步骤：
初始化：将所有单元格的 val 值直接赋给 dpmin 和 dpmax。
计算块大小：通过 mm 数组记录每行和每列的最大块大小。mm[i] 表示第 i 行的最大块大小，mm[j] 表示第 j 列的最大块大小。
预处理动态规划表：从小块到大块逐步构建。对于每个块大小 ii 和 jj，从 1 到最大块大小：
1，则更新更大的块的最小和最大值。查询最大值：rmq1 函数接受矩形区域的四个顶点，计算所需块的大小 k1 和 k2，然后从预处理表中获取最大值。
查询最小值：rmq2 函数同样接受四个顶点，使用预处理表获取最小值。
通过动态规划预处理，实现了高效的二维范围查询。每个查询的时间复杂度为 O(1)，预处理时间复杂度为 O(N log N)。这种方法在处理大量查询时表现优异，能够快速响应用户需求。
转载地址：http://euxfk.baihongyu.com/