那里做一元云购网站,wordpress怎么样建站内战,做网站运营话术,网站被qq拦截 做301RMQ
RMQ 是英文 Range Maximum/Minimum Query 的缩写#xff0c;表示区间最大#xff08;最小#xff09;值。使用倍增思想解决 RMQ 问题的方法是 ST 表#xff08;Sparse Table#xff0c; 稀疏表 #xff09;。ST 表是用于解决 可重复贡献问题 的数据结构。 可重复贡献…RMQ
RMQ 是英文 Range Maximum/Minimum Query 的缩写表示区间最大最小值。使用倍增思想解决 RMQ 问题的方法是 ST 表Sparse Table 稀疏表 。ST 表是用于解决 可重复贡献问题 的数据结构。 可重复贡献问题 是指对于运算 opt \operatorname{opt} opt满足 x opt x x x\operatorname{opt} xx xoptxx则对应的区间询问就是一个可重复贡献问题。例如最大值有 max ( x , x ) x \max(x,x)x max(x,x)x g c d gcd gcd 有 gcd ( x , x ) x \operatorname{gcd}(x,x)x gcd(x,x)x所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质如果求区间和的时候采用的预处理区间重叠了则会导致重叠部分被计算两次。另外 opt \operatorname{opt} opt 还必须满足结合律才能使用 ST 表求解。 题目链接
题目链接【模板】ST 表
题目描述
这是一道 ST 表经典题——静态区间最大值
请注意最大数据时限只有 0.8s数据强度不低请务必保证你的每次查询复杂度为 O ( 1 ) O(1) O(1)。若使用更高时间复杂度算法不保证能通过。
如果您认为您的代码时间复杂度正确但是 TLE可以尝试使用快速读入
inline int read()
{int x0,f1;char chgetchar();while (ch0||ch9){if (ch-) f-1;chgetchar();}while (ch0ch9){xx*10ch-48;chgetchar();}return x*f;
}函数返回值为读入的第一个整数。
快速读入作用仅为加快读入并非强制使用。
题目描述
给定一个长度为 N N N 的数列和 M M M 次询问求出每一次询问的区间内数字的最大值。
输入格式
第一行包含两个整数 N , M N,M N,M分别表示数列的长度和询问的个数。
第二行包含 N N N 个整数记为 a i a_i ai依次表示数列的第 i i i 项。
接下来 M M M 行每行包含两个整数 l i , r i l_i,r_i li,ri表示查询的区间为 [ l i , r i ] [l_i,r_i] [li,ri]。
输出格式
输出包含 M M M 行每行一个整数依次表示每一次询问的结果。
样例 #1
样例输入 #1
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8样例输出 #1
9
9
7
7
9
8
7
9提示
对于 30 % 30\% 30% 的数据满足 1 ≤ N , M ≤ 10 1\le N,M\le 10 1≤N,M≤10。
对于 70 % 70\% 70% 的数据满足 1 ≤ N , M ≤ 10 5 1\le N,M\le {10}^5 1≤N,M≤105。
对于 100 % 100\% 100% 的数据满足 1 ≤ N ≤ 10 5 1\le N\le {10}^5 1≤N≤105 1 ≤ M ≤ 2 × 10 6 1\le M\le 2\times{10}^6 1≤M≤2×106 a i ∈ [ 0 , 10 9 ] a_i\in[0,{10}^9] ai∈[0,109] 1 ≤ l i ≤ r i ≤ N 1\le l_i\le r_i\le N 1≤li≤ri≤N。
算法思想
ST 表基于倍增思想可以做到 O ( n log n ) O(n\log n) O(nlogn) 预处理 O ( 1 ) O(1) O(1) 回答每个询问。但是不支持修改操作。
基于倍增思想考虑如何求出区间最大值。可以发现如果按照一般的倍增流程每次跳 2 i 2^i 2i步的话询问时的复杂度仍旧是 O ( log n ) O(\log n) O(logn)效率较低。
由于区间最大值是一个具有可重复贡献性质的问题。哪怕用来求解的预处理区间有重叠部分只要这些区间合并是所求的区间最终计算出的答案就是正确的。举个例子 区间 [ 2 , 5 ] [2,5] [2,5]的最大值为 5 5 5区间 [ 4 , 7 ] [4,7] [4,7]的最大值为 7 7 7区间 [ 2 , 7 ] [2,7] [2,7]的最大值为 max { 5 , 7 } 7 \max\{5,7\}7 max{5,7}7。
通过ST表使用至多两个预处理过的区间就可以覆盖询问区间也就是说询问时的时间复杂度可以被降至 O ( 1 ) O(1) O(1)在处理有大量询问的题目时十分有效。
预处理ST表
状态表示 f [ i ] [ j ] f[i][j] f[i][j]表示区间 [ i , i 2 j − 1 ] [i,i2^j-1] [i,i2j−1]的最大值。
状态计算
要计算区间 [ i , i 2 j − 1 ] [i,i2^j-1] [i,i2j−1]的最大值区间大小为 2 j 2^j 2j相当于从位置 i i i跳了 2 j − 1 2^j-1 2j−1 步依据倍增的思想可以将整个区间一分为二左侧区间 [ i , i 2 j − 1 − 1 ] [i,i2^{j-1}-1] [i,i2j−1−1]右侧区间 [ i 2 j − 1 , i 2 j − 1 ] [i2^{j-1},i2^j-1] [i2j−1,i2j−1]大小均为 2 j − 1 2^{j-1} 2j−1如下图所示 那么状态转移方程 f [ i ] [ j ] m a x { f [ i ] [ j − 1 ] , f [ i 2 j − 1 ] [ j − 1 ] } f[i][j]max\{f[i][j-1],f[i2^{j-1}][j-1]\} f[i][j]max{f[i][j−1],f[i2j−1][j−1]}
初始状态 f [ i ] [ 0 ] a i f[i][0]a_i f[i][0]ai
查询区间最值
对于每个询问 [ L , R ] [L,R] [L,R]把它成两个部分 [ L , L 2 k − 1 ] [L,L2^k-1] [L,L2k−1]与 [ R − 2 k 1 , R ] [R-2^k1,R] [R−2k1,R]其中 k ⌊ l o g 2 ( R − L 1 ) ⌋ k\lfloor log_2(R-L1)\rfloor k⌊log2(R−L1)⌋两部分的最值就是答案。
时间复杂度
预处理 ST 表的时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)回答每个询问的时间复杂度 O ( 1 ) O(1) O(1)
代码实现
#include iostream
#include cmath
using namespace std;
const int N 1e5 10, M 20;
int n, a[N], f[N][M];
//创建ST表
void create() {//初始状态//f[i][0]表示从i开始长度为2^0的区间最值为a[i]本身for(int i 1; i n; i ) f[i][0] a[i];int k log2(n);//枚举区间长度指数jfor(int j 1; j k; j )for(int i 1; i (1 j) - 1 n; i )f[i][j] max(f[i][j - 1], f[i (1 j - 1)][j - 1]);
}
//利用ST表查询区间[L,R]的最大值
int query(int L, int R) {int k log2(R - L 1);return max(f[L][k], f[R - (1 k) 1][k]);
}
int main()
{int m;cin n m;for(int i 1; i n; i ) scanf(%d, a i);;create();while(m --) {int L, R;scanf(%d%d, L, R);printf(%d\n, query(L, R));}
}
