欢迎访问我的博客：blog.chungzh.cn

这题最好的解法是 $O(n)$ 的单调队列。但是 ST 表也可以做，需要 $O(n \log n)$ 预处理，$O(1)$ 询问。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int logn[1000005], f[1000005][21];
void init() {
	logn[1] = 0;
	for (int i = 2; i <= n; i++) logn[i] = logn[i/2]+1;
}
int main() {
	cin >> n >> m;
	init();
	for (int i = 1; i <= n; i++)
		cin >> f[i][0];
	for (int j = 1; j <= 20; j++) {
		for (int i = 1; i+(1<<j)-1 <= n; i++) {
			f[i][j] = min(f[i][j-1], f[i+(1<<(j-1))][j-1]);
		}		
	}
	for (int i = m; i <= n; i++) {
		int lg = logn[m];
		cout << min(f[i-m+1][lg], f[i-(1<<lg)+1][lg]) << endl;
	}
	return 0;
}