P2251 质量检测
题目大意
给定长度为 \(N\) 的数组 \(A\)，定义数组 \(Q\)，\(Q_i = \min{\{A_1,A_2,\cdots,A_i\}}\)。对于每个 \(i\left(1 \le i \le N-M+1\right)\)，输出 \(Q_{i}\)，\(M\) 是给定的常数。
样例
输入
10 4
16 5 6 9 5 13 14 20 8 12
输出
5
5
5
5
5
8
8
解决方法
发现题目是要获取每个区间内最小值，于是想到 ST表，板子稍作修改即可。
代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[100010], ST[100010][22], lg[100010];
int main() {
cin >> n >> m;
lg[0] = -1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
lg[i] = lg[i / 2] + 1;
}
for (int i = 0; i <= n; i++) {
ST[i][0] = a[i];
//cout << ST[i][0] << endl;
}
for (int j = 1; j <= 17; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
ST[i][j] = min(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
}
}
int l = 1, r = m;
while (l <= n - m + 1 && r <= n) {
int t = lg[r - l + 1];
cout << min(ST[l][t], ST[r - (1 << t) + 1][t]) << endl;
l++, r++;
}
return 0;
}