【模板】静态区间最值【牛客tracker 每日一题】

【模板】静态区间最值

时间限制：5秒 空间限制：1024M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

对于给定的长度为n nn的数组 {a 1 , a 2 , … , a n a_1,a_2,…,a_na1​,a2​,…,an​} ，你需要构建一个能够维护区间最大/最小值信息的数据结构，使得其能支持：

1. 区间最小值查询：输出[ l , r ] [l,r][l,r]这个区间中的最小元素，即m i n ⁡ min⁡min⁡{a l , a l + 1 , … , a r a_l,a_{l+1},…,a_ral​,al+1​,…,ar​} ；
2. 区间最大值查询：输出[ l , r ] [l,r][l,r]这个区间中的最大元素，即m a x maxmax⁡{a l , a l + 1 , … , a r a_l,a_{l+1},…,a_ral​,al+1​,…,ar​} 。

提示本题为『离线 ‖ 静态：仅询问 ‖区间最值』模板题，我们可以使用S T STST表解决，预期实现时间复杂度为O ( n l o g ⁡ n ) O(nlog⁡n)O(nlog⁡n)。您也可以尝试使用已知的O ( n ) O(n)O(n)复杂度做法通过本题。

输入描述：

第一行输入两个整数n , q ( 1 ≦ n , q ≦ 5 × 1 0 5 ) n,q(1≦n,q≦5×10^5)n,q(1≦n,q≦5×105)代表数组中的元素数量、操作次数。
第二行输入n nn个整数a 1 , a 2 , … , a n ( − 1 0 9 ≦ a i ≦ 1 0 9 ) a_1,a_2,…,a_n(−10^9≦a_i≦10^9)a1​,a2​,…,an​(−109≦ai​≦109)代表初始数组。
此后q qq行，每行先输入一个整数o p ( 1 ≦ o p ≦ 2 ) op(1≦op≦2)op(1≦op≦2)代表操作编号，随后：

• 若o p = 1 op=1op=1，在同一行输入两个整数l , r ( 1 ≦ l ≦ r ≦ n ) l,r(1≦l≦r≦n)l,r(1≦l≦r≦n)代表区间最小值查询；
• 若o p = 2 op=2op=2，在同一行输入两个整数l , r ( 1 ≦ l ≦ r ≦ n ) l,r(1≦l≦r≦n)l,r(1≦l≦r≦n)代表区间最大值查询。

输出描述：

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

示例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

说明：

对于第一次操作，查询1 , 1 , 4 , 5 , 1 , 4 {1,1,4,5,1,4}1,1,4,5,1,4（单点查询）最小值，答案输出1 11；
对于第二次操作，查询1 , 1 , 4 , 5 , 1 , 4 {1,1,4,5,1,4}1,1,4,5,1,4最小值，答案输出4 44；
对于第三次操作，查询1 , 1 , 4 , 5 , 1 , 4 {1,1,4,5,1,4}1,1,4,5,1,4（单点查询）最大值，答案输出5 55；
对于第四次操作，查询1 , 1 , 4 , 5 , 1 , 4 {1,1,4,5,1,4}1,1,4,5,1,4（全局查询）最大值，答案输出5 55。

解题思路

采用S T STST表（稀疏表）解决静态区间最值查询问题，首先预处理对数数组L o g LogLog（通过递推快速得到每个数的二进制对数，避免查询时重复计算），再构建两个S T STST表s t m i n st_{min}stmin​和s t m a x st_{max}stmax​，其中s t m i n [ i ] [ j ] st_{min}[i][j]stmin​[i][j]表示从i ii开始长度为2 j 2^j2j的区间最小值，s t m a x [ i ] [ j ] st_{max}[i][j]stmax​[i][j]表示对应区间最大值，通过递推式由j − 1 j-1j−1层的子区间最值合并得到j层的最值；对于每次查询，计算区间长度的对数k kk，将查询区间拆分为两个长度为2 k 2^k2k的重叠子区间，取其最值作为结果（最小值查询取两个子区间最小值的较小者，最大值查询取较大者）；该方法预处理时间复杂度为O ( n l o g n ) O(nlogn)O(nlogn)，单次查询时间复杂度为O ( 1 ) O(1)O(1)，适配n nn和q qq达5 e 5 5e55e5的大规模输入，高效精准输出每个区间的最值。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=5e5+10;constll M=20;ll st_min[N][M];ll st_max[N][M];ll Log[N],arr[N];ll n,q;voidinit_log(){Log[1]=0;for(ll i=2;i<=n;i++)Log[i]=Log[i/2]+1;}voidbuild_st(){for(ll i=1;i<=n;i++){st_min[i][0]=arr[i];st_max[i][0]=arr[i];}for(ll j=1;j<M;j++)for(ll i=1;i+(1<<j)-1<=n;i++){st_min[i][j]=min(st_min[i][j-1],st_min[i+(1<<(j-1))][j-1]);st_max[i][j]=max(st_max[i][j-1],st_max[i+(1<<(j-1))][j-1]);}}llquery_min(ll l,ll r){ll k=Log[r-l+1];returnmin(st_min[l][k],st_min[r-(1<<k)+1][k]);}llquery_max(ll l,ll r){ll k=Log[r-l+1];returnmax(st_max[l][k],st_max[r-(1<<k)+1][k]);}intmain(){if(!(cin>>n>>q))return0;for(ll i=1;i<=n;i++)cin>>arr[i];init_log();build_st();ll op,l,r;while(q--){cin>>op>>l>>r;if(op==1)cout<<query_min(l,r)<<endl;elsecout<<query_max(l,r)<<endl;}return0;}