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;
}