rmq稀疏表

#include <bits/stdc++.h>
#define Maxn 100010
using namespace std;
int n, m, a[Maxn], f[Maxn][33];
int Query(int l, int r) {
	int len = r - l + 1, w = 0;
	while((1 << w) <= len) ++w;
	--w;
	return min(f[l][w], f[r - (1 << (w)) + 1][w]);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		f[i][0] = a[i]; // f[i][j] ====> 从i开始 长度为 2^j 的区间中最大值 
	}
	for(int j = 1; j <= 20; ++j) {
		for(int i = 1; i <= n; ++i) {
			if(i + (1 << j) - 1 <= n) {
				f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	int l = 1,r = m;
	while(l <= n - m + 1 and r <= n) {
		printf("%d\n", Query(l, r));
		l++;r++;
	}
	return 0;
}

单调队列方法：

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    deque<int> dq; // 存放窗口内候选下标，使 A[dq] 单调递增

    for (int i = 0; i < N; i++) {
        // 1. 将 i 之前 >= A[i] 的下标从队尾弹出
        while (!dq.empty() && A[dq.back()] >= A[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // 2. 弹出不在当前窗口 [i-M+1, i] 内的队首
        int L = i - M + 1;
        if (dq.front() < L) {
            dq.pop_front();
        }

        // 3. 当 i >= M-1 时，窗口已满，可以输出最小值
        if (i >= M - 1) {
            cout << A[dq.front()] << "\n";
        }
    }

    return 0;
}