好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

输入一串数字，给你 $M$ 个询问，每次询问给出两个数字 $X, Y$，要求输出 $[X, Y]$ 这段区间内的最大值。

输入格式

第一行两个整数 $N, M$，表示数字的个数和要询问的次数；

第二行包含 $N$ 个整数，表示数列；

接下来 $M$ 行，每行两个整数 $X, Y$，表示一个询问的区间。

输出格式

输出共 $M$ 行，每行输出一个整数，表示对应区间内的最大值。

样例

样例输入

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

样例输出

5
8

样例说明

数列：$[3, 2, 4, 5, 6, 8, 1, 2, 9, 7]$。

询问 1：$[1, 4]$ 区间为 $3,2,4,5$，最大值是 $5$。
询问 2：$[3, 8]$ 区间为 $4,5,6,8,1,2$，最大值是 $8$。

数据范围

对于全部数据：

• $1 \le N \le 10^5$
• $1 \le M \le 10^6$
• $1 \le X \le Y \le N$
• 数列中的数字不超过 C/C++ 的 int 范围

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$（512 MB）

提示
此题为 区间最值查询（RMQ） 问题，由于 $M$ 很大（$10^6$），需要 $O(1)$ 或 $O(\log N)$ 的查询。

方法一：线段树

• 构建线段树，每个节点维护区间最大值；
• 查询时递归合并区间最大值；
• 复杂度：建树 $O(N)$，查询 $O(\log N)$，总复杂度 $O(N + M\log N)$，在 $M=10^6$ 时可能接近极限，但常数较小通常可过。

方法二：ST表（Sparse Table）

• 预处理 $f[i][j]$ 表示区间 $[i, i+2^j-1]$ 的最大值；
• 查询 $[l, r]$ 时，令 $k = \lfloor \log_2(r-l+1) \rfloor$，答案 $= \max(f[l][k], f[r-2^k+1][k])$；
• 复杂度：预处理 $O(N \log N)$，查询 $O(1)$，总复杂度 $O(N \log N + M)$，适合 $M$ 很大的情况。

方法三：树状数组（需特殊处理）
树状数组通常用于前缀和，但可以通过维护区间最值的方式实现 RMQ，不过复杂度为 $O(\log N)$，且只能处理特定类型（如不可修改或特殊修改），本题为静态 RMQ，不推荐树状数组。

推荐方法：
由于 $M$ 高达 $10^6$，应选择 ST表 以获得 $O(1)$ 查询。

ST表实现步骤：

1. 预处理 $\log_2$ 表（或直接用 __lg 函数）；
2. 初始化 $f[i][0] = a[i]$；
3. 递推：$f[i][j] = \max(f[i][j-1], f[i+2^{j-1}][j-1])$；
4. 查询 $[l, r]$：$k = \log_2(r-l+1)$，返回 $\max(f[l][k], f[r-2^k+1][k])$。

注意：

• 输入输出量极大，必须使用快速 IO（scanf/printf 或关闭同步的 cin/cout）；
• 内存：ST 表大小 $N \times (\lfloor \log_2 N \rfloor + 1)$，$N=10^5$ 时约 $10^5 \times 17 \approx 1.7\times 10^6$ 个 int，约 6.8 MB，可以接受；
• 数列元素在 int 范围内，但中间运算用 int 即可。