文章目录
- RMQ问题
- ST算法
- 模板
- 例题
- P2251 质量检测
- P1816 忠诚
- P2216 [HAOI2007]理想的正方形
RMQ问题
RMQ（Range Minimum/Maximum Query）问题，是求区间最大值或最小值，即范围最值问题。暴力解法是对每个询问区间循环求解，设区间长度n ，询问次数m ，则复杂度是O(nm) 。一般还可以使用线段树求解，复杂度是O(mlogn) 。但还有一种更简便的ST算法，预处理复杂度是O(nlogn) ，查询O(1) 。
ST算法
ST（Sparse Table）即稀疏表，运用了动态规划的思想，设dp[i][j] 表示第i 处开始的2^j 个数字的最值，i 是开始位置，j 是延伸长度，dp[i][0] 则是原数组a[i] 本身，是边界。原理类似倍增，首先比较每2个元素的最值，然后再通过比较这2个最值，得到4个元素的最值，以此类推8个、16个……。
状态转移方程：dp[i][j]=min(dp[i][j-1],dp[i 2^j][j-1]) 。 即长度为2^j 区间的最值是左右两半长度为2^{j-1} 子区间中最值较小的一个，而两个子区间的起始位置不难推出，分别是i 和i 2^{j-1} 。max最大值同理。
查询时，需要找到两个区间完全覆盖[l,r] ，也就是需要计算出k ，使2^k<r-l 1<2^{k 1} ，换句话说就是，从左端点l开始的2^k个数和以右端点结尾的2^k 个数覆盖区间[l,r]，即min(dp[l][k],dp[r-2^k 1][k])。
模板
洛谷P3865 【模板】ST表
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
ll a[maxn];
ll dp[maxn][21];
void st(int n) {
for (int i = 1; i <= n; i )
dp[i][0] = a[i];
for (int j = 1; j <= 21; j ) {
for (int i = 1; i (1 << j) - 1 <= n; i ) {
dp[i][j] = max(dp[i][j - 1], dp[i (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r) {
int k = log2(r - l 1);
return max(dp[l][k], dp[r - (1 << k) 1][k]);
}
int main() {
int n, m, l, r;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i )
scanf("%lld", &a[i]);
st(n);
while (m--) {
scanf("%d%d", &l, &r);
printf("%lldn", query(l, r));
}
return 0;
}例题
P2251 质量检测
洛谷P2251 质量检测
题目描述 为了检测生产流水线上总共 NN 件产品的质量，我们首先给每一件产品打一个分数 AA 表示其品质，然后统计前 MM 件产品中质量最差的产品的分值 Q[m] = min{A_1, A_2, … A_m}以及第 2 至第 M 1件的Q[m 1], Q[m 2] Q[m 1],Q[m 2]… 最后统计第 N - M 1至第N件的Q[n]。根据 Q 再做进一步评估。 请你尽快求出 Q 序列。 输入格式 输入共两行。 第一行共两个数 N、M，由空格隔开。含义如前述。 第二行共 N 个数，表示 N 件产品的质量。 输出格式 输出共 N - M 1行。 第 1 至 N - M 1行每行一个数，第i行的数 Q[i M - 1]。含义如前述。 输入输出样例 输入 #1 10 4 16 5 6 9 5 13 14 20 8 12 输出 #1 5 5 5 5 5 8 8 说明/提示 [数据范围] 30%的数据，N≤1000 100%的数据，N≤100000 100%的数据，M≤N,A≤1000000
用单调队列也能做，ST模板练手。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int maxn = 1000006;
int dp[maxn][21];
int n, m, k;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i )
cin >> dp[i][0];
for (int j = 1; j <= 21; j )
for (int i = 1; i (1 << j) - 1 <= n; i )
dp[i][j] = min(dp[i][j - 1], dp[i (1 << (j - 1))][j - 1]);
k = log2(m);
for (int i = 1; i m - 1 <= n; i )
cout << min(dp[i][k], dp[i m - (1 << k)][k]) << "n";
return 0;
}（
插播反爬信息）博主CSDN地址：https://wzlodq.blog.csdn.net/
P1816 忠诚
洛谷P1816 忠诚
题目描述 老管家是一个聪明能干的人。他为财主工作了整整10年。财主为了让自已账目更加清楚，要求管家每天记 k次账。由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按 1, 2, 3… 编号，然后不定时的问管家问题，问题是这样的：在a 到b 号账中最少的一笔是多少？为了让管家没时间作假，他总是一次问多个问题。 输入格式 输入中第一行有两个数 m, nm,n，表示有 mm 笔账 nn 表示有 nn 个问题。 第二行为m个数，分别是账目的钱数。 后面 n 行分别是 n 个问题，每行有 2个数字说明开始结束的账目编号。 输出格式 在一行中输出每个问题的答案，以一个空格分割。 输入输出样例 输入 #1 10 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10 输出 #1 2 3 1 说明/提示 对于100% 的数据，m≤105 ，n≤105
练手 1
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int maxn = 100005;
int dp[maxn][21];
int n, m, l, r, k;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i )
cin >> dp[i][0];
for (int j = 1; j <= 21; j )
for (int i = 1; i (1 << j) - 1 <= n; i )
dp[i][j] = min(dp[i][j - 1], dp[i (1 << (j - 1))][j - 1]);
while (m--) {
cin >> l >> r;
k = log2(r - l 1);
cout << min(dp[l][k], dp[r - (1 << k) 1][k]) << " ";
}
return 0;
}P2216 [HAOI2007]理想的正方形
洛谷P2216 [HAOI2007]理想的正方形
题目描述 有一个ab的整数组成的矩阵，现请你从中找出一个nn的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 输入格式 第一行为3个整数，分别表示a,b,n的值 第二行至第a 1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。 输出格式 仅一个整数，为ab矩阵中所有“nn正方形区域中的最大整数和最小整数的差值”的最小值。 输入输出样例 输入 #1 5 4 2 1 2 5 6 0 17 16 0 16 17 2 1 2 10 2 1 1 2 2 2 输出 #1 1 说明/提示 问题规模 （1）矩阵中的所有数都不超过1,000,000,000 （2）20%的数据2<=a,b<=100,n<=a,n<=b,n<=10 （3）100%的数据2<=a,b<=1000,n<=a,n<=b,n<=100
二维RMQ
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int a, b, n, k;
int v[1003][1003];
int maxv[1003][1003], minv[1003][1003];
int query(int x, int y) {
int mx = 0, mi = 0;
mx = max(maxv[x][y], max(maxv[x n - (1 << k)][y n - (1 << k)], max(maxv[x n - (1 << k)][y], maxv[x][y n - (1 << k)])));
mi = min(minv[x][y], min(minv[x n - (1 << k)][y n - (1 << k)], min(minv[x n - (1 << k)][y], minv[x][y n - (1 << k)])));
return mx - mi;
}
int main(){
cin >> a >> b >> n;
for (int i = 0; i < a; i )
for (int j = 0; j < b; j ) {
cin >> v[i][j];
maxv[i][j] = minv[i][j] = v[i][j];
}
k = log2(n);
for (int ki = 0; ki < k; ki )
for (int i = 0; i (1 << ki) < a; i )
for (int j = 0; j (1 << ki) < b; j ) {
maxv[i][j] = max(maxv[i][j], max(maxv[i (1 << ki)][j (1 << ki)], max(maxv[i (1 << ki)][j], maxv[i][j (1 << ki)])));
minv[i][j] = min(minv[i][j], min(minv[i (1 << ki)][j (1 << ki)], min(minv[i (1 << ki)][j], minv[i][j (1 << ki)])));
}
int ans = INT_MAX;
for (int i = 0; i <= a - n; i )
for (int j = 0; j <= b - n; j )
ans = min(ans, query(i, j));
cout << ans;
return 0;
}
