首页 > 试题广场 >

【模板】静态区间最值

[编程题]【模板】静态区间最值

热度指数：2389 时间限制：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)$ 复杂度做法通过本题。

输入描述:

第一行输入两个整数  代表数组中的元素数量、操作次数。
第二行输入  个整数  代表初始数组。
此后  行，每行先输入一个整数  代表操作编号，随后：
若  ，在同一行输入两个整数  代表区间最小值查询；
若  ，在同一行输入两个整数  代表区间最大值查询。

输出描述:

对于每一次询问，输出一行一个整数代表区间最值。

示例1

输入

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

输出

说明

对于第一次操作，查询 （单点查询）最小值，答案输出  ；
对于第二次操作，查询  最小值，答案输出  ；
对于第三次操作，查询 （单点查询）最大值，答案输出  ；
对于第四次操作，查询 （全局查询）最大值，答案输出  。

算法知识视频讲解

FoolBlade

发表于 2025-12-14 00:50:53

template<typename T> class ST{ public: vector<vector<T> > st; int sz; function<T(T,T)> op;//op can be max,min,gcd, 展开全文

丨阿伟丨

发表于 2025-09-08 14:48:30

题目链接 PEEK61 【模板】静态区间最值题目描述给定一个长度为的静态数组。有次查询，每次查询给定一个区间，要求回答该区间的最大值或最小值。解题思路本题是静态区间最值查询（Range Minimum/Maximum Query, RMQ）的模板题。由于数组内容不会改变，且查询次展开全文

realrole

发表于 2025-12-14 01:48:11

#include <iostream> using namespace std; int a[500050]; int st_min[20][500050]; int st_max[20][500050]; int log_table[500050]; int main() { 展开全文

孩子不会python

发表于 2025-12-14 12:34:13

# { # "name": "【模板】静态区间最值", # "group": "NowCoder", # "url": "https://www.nowcoder.c 展开全文

软件25_4刘卓生

发表于 2025-12-14 12:59:45

此题可用线段树来解决，标准线段树模板 #include <bits/stdc++.h> using namespace std; const int total=1e5+7; int a[5*total]; struct node{ int mx; int mi; }tr 展开全文

周康禧

发表于 2025-12-14 16:59:28

#include <bits/stdc++.h> using namespace std; using ll = long long int; using ld = long double; using PII=pair<ll,ll>; using PIII=pair< 展开全文

caozq1

发表于 2025-12-14 22:38:15

妥妥的线段树 / ST表板子题。本蒟蒻写题时脑子抽了没想到简洁的ST表写法。只好写线段树了。。 #include<bits/stdc++.h> using namespace std; const int N = 4e6 + 10; int a[N]; int maxx[N]; i 展开全文

bing糖雪狸

发表于 2025-12-14 09:45:35

#include<bits/stdc++.h> #define il inline #define endl '\n' using namespace std; #define pb push_back #define fastio \ ios::sync_with_stdio(f 展开全文

quchen666

发表于 2025-12-14 11:31:45

#include <bits/stdc++.h> using namespace std; const int N = 3e6+10; int q,n; int a[N]; int mx[N],mn[N]; void up(int i) { mx[i] = max(mx[i&l 展开全文

IA3000

发表于 2025-12-14 11:56:08

#include <bits/stdc++.h> using namespace std; const int N= 5e5+5,inf=1e9+7; int n,q,len; int a[N]; int mx[N],mn[N]; void solve(){ cin> 展开全文

问题信息

难度：

2条回答 12收藏 14浏览

【模板】静态区间最值

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题