解题思路

思路

本题的操作全部是静态区间最大值询问。随着数据规模增大，可以依次采用逐询问扫描、分块预处理和 ST 表，把单次询问复杂度从线性降低到平方根，最终降低到常数。

做法

子任务 1：直接扫描询问区间

对每次询问，从左端点走到右端点并维护当前最大值即可。该方法无需预处理，单次询问的时间复杂度为 $O(N)$，总时间复杂度为 $O(NM)$，适用于 $N,M\le 10$。

子任务 2：分块

把数列按约为 $\sqrt N$ 的长度划分为若干块，并预处理每一块的最大值。

回答询问时，左右两端不足整块的部分逐项扫描，中间完整覆盖的块直接使用块最大值。一次询问至多扫描两个零散段和 $O(\sqrt N)$ 个整块，因此总时间复杂度为 $O(N+M\sqrt N)$，空间复杂度为 $O(N)$。这一做法可以处理 $N,M\le 10^5$ 的子任务。

子任务 3：ST 表

记 $f_{k,i}$ 为从位置 $i$ 开始、长度为 $2^k$ 的区间最大值。初始时 $f_{0,i}=a_i$。对于 $k>0$，长度为 $2^k$ 的区间可以拆成两个相邻、长度均为 $2^{k-1}$ 的区间，因此其最大值由前一层的两个值取最大得到。

预处理所有层需要 $O(N\log N)$ 时间和 $O(N\log N)$ 空间。

对于询问 $[l,r]$，令 $k=\lfloor\log_2(r-l+1)\rfloor$。区间两端各取一个长度为 $2^k$ 的区间，这两个区间的并集覆盖整个询问区间。最大值运算满足幂等性，即重复覆盖同一位置不会改变结果，所以答案是这两个预处理值的最大值。

预先计算所有长度的整数对数后，每次询问只需 $O(1)$ 时间。总时间复杂度为 $O(N\log N+M)$，空间复杂度为 $O(N\log N)$。

正确性证明

首先证明预处理值正确。对 $k$ 归纳：当 $k=0$ 时，区间只含一个元素，定义显然正确。若第 $k-1$ 层均正确，则长度为 $2^k$ 的区间由两个长度为 $2^{k-1}$ 的相邻区间组成；取两者最大值正好得到整个区间最大值，因此第 $k$ 层也正确。

再考虑任意询问 $[l,r]$。按上述方式选择的左、右两个长度为 $2^k$ 的区间都位于 $[l,r]$ 内，并且它们的并集覆盖 $[l,r]$。每个区间的最大值已由预处理正确求出；对二者再取最大值，就得到 $[l,r]$ 中所有元素的最大值。由此算法对每次询问都输出正确答案。

复杂度

满分算法的预处理时间复杂度为 $O(N\log N)$，每次询问为 $O(1)$，总时间复杂度为 $O(N\log N+M)$；空间复杂度为 $O(N\log N)$。

数值范围

算法只比较输入整数，不进行加法或乘法。$a_i\le 10^9$，使用 32 位有符号整数即可保存数组值和答案；下标、长度及询问数量也均在 32 位有符号整数范围内。