首页 > 试题广场 >

【模板】静态区间最值

[编程题]【模板】静态区间最值
  • 热度指数：2468 时间限制：C/C++ 5秒，其他语言10秒 空间限制：C/C++ 1024M，其他语言2048M
  • 算法知识视频讲解
\hspace{15pt}对于给定的长度为 n 的数组 \{a_1,a_2,\dots,a_n\} ，你需要构建一个能够维护区间最大/最小值信息的数据结构，使得其能支持：
\hspace{22.5pt}_\texttt{1.}\区间最小值查询：输出 [l,r] 这个区间中的最小元素，即 \min \{ a_l, a_{l+1}, \dots, a_r\} ；
\hspace{22.5pt}_\texttt{2.}\区间最大值查询：输出 [l,r] 这个区间中的最大元素，即 \max \{ a_l, a_{l+1}, \dots, a_r\} 。
提示 \hspace{15pt}本题为『离线 ‖ 静态：仅询问 ‖ 区间最值』模板题，我们可以使用 \sf ST 表解决，预期实现时间复杂度为 \mathcal O \left( n \log n \right) 。您也可以尝试使用已知的 \mathcal O(n) 复杂度做法通过本题。

输入描述:
\hspace{15pt}第一行输入两个整数 n,q \left( 1 \leqq n,q \leqq 5 \times 10^5\right) 代表数组中的元素数量、操作次数。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( -10^9 \leqq a_i \leqq 10^9 \right) 代表初始数组。
\hspace{15pt}此后 q 行，每行先输入一个整数 op \left( 1 \leqq op \leqq 2 \right) 代表操作编号，随后：
\hspace{22.5pt}\bullet\若 op=1 ，在同一行输入两个整数 l, r \left( 1 \leqq l \leqq r \leqq n \right) 代表区间最小值查询；
\hspace{22.5pt}\bullet\若 op=2 ，在同一行输入两个整数 l, r \left( 1 \leqq l \leqq r \leqq n \right) 代表区间最大值查询。


输出描述:
\hspace{15pt}对于每一次询问，输出一行一个整数代表区间最值。
示例1

输入

6 4
1 1 4 5 1 4
1 1 1
1 3 4
2 4 4
2 1 6

输出

1
4
5
5

说明

\hspace{15pt}对于第一次操作，查询 \{{\color{orange}{1}}, 1, 4, 5, 1, 4 \}（单点查询）最小值，答案输出 1 ；
\hspace{15pt}对于第二次操作，查询 \{1, 1, {\color{orange}{4, 5}}, 1, 4 \} 最小值，答案输出 4 ；
\hspace{15pt}对于第三次操作，查询 \{1, 1, 4, {\color{orange}{5}}, 1, 4 \}（单点查询）最大值，答案输出 5 ；
\hspace{15pt}对于第四次操作，查询 \{{\color{orange}{1, 1, 4, 5, 1, 4}} \}（全局查询）最大值，答案输出 5 。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 26浏览

热门推荐

相关试题

【模板】静态区间最值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号