C++ / 固定记录的区间最高值 算法挑战

固定记录的区间最高值

在没有分步提示的新场景中，独立应用本单元的数据结构。

需求与输入输出

第一行 n q，随后 n 个整数，数据之后不再修改。每个查询一行 l r，输出闭区间最大值。n、q≤100000，元素绝对值不超过 10⁹。

使用 C++17。输入符合协议，编号从 1 开始；除特别说明外，n、q 均不超过 100000。不要输出额外提示语。

样例输入

4 3
3 8 2 6
1 4
3 4
2 2

样例输出

8
6
8

验收要求

• 正确处理单元素、空结构或无匹配情况。
• 更新后查询反映最新状态；多个测试之间不共享状态。
• 累计量使用 long long。

实现建议

稀疏表按 2 的幂建立区间摘要，查询用两个可重叠区间覆盖；本题的最大值运算允许重叠。

先手工推演样例，再独立编写实现。通过测试后需正式提交，才计入编程成果。