ST表也能过!

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5, MAXX = 21; // MAXX为log2(MAXN)
int n, k; // 元素个数 窗口大小
int a[MAXN]; // 序列元素
int st_max[MAXN][MAXX]; // 查询最大值的ST表
int st_min[MAXN][MAXX]; // ~ ~ ~ 小~ ~ ~ ~
int Log2[MAXN]; // 预处理每个数的log
void init_st() {
	Log2[1] = 0;
	Log2[2] = 1;
	for (int i = 3; i <= MAXN; i++) {
		Log2[i] = Log2[i / 2] + 1;
	}
	// 初始化ST表的第一层
	for(int i = 0; i < n; i++) {
		st_max[i][0] = a[i];
		st_min[i][0] = a[i];
	}
	// 建立ST表
	for(int j = 1; j < MAXX; j++) {
		for (int i = 0; i + (1 << j) <= n; i++) { 
			int pos = i + (1 << (j - 1)); 
			st_max[i][j] = max(st_max[i][j - 1], st_max[pos][j - 1]);
			st_min[i][j] = min(st_min[i][j - 1], st_min[pos][j - 1]);
		}
	}
}
int query_max(int l, int r) {
	int j = Log2[r - l + 1];
	return max(st_max[l][j], st_max[r - (1 << j) + 1][j]);
}int query_min(int l, int r) { 
	int j = Log2[r - l + 1];
	return min(st_min[l][j], st_min[r - (1 << j) + 1][j]);
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	init_st();
    for(int i = 0; i + k - 1 < n; i++) {
        cout << query_min(i, i + k - 1) << ' ';
    }
    cout << '\n';
    for(int i = 0; i + k - 1 < n; i++) {
        cout << query_max(i, i + k - 1) << ' ';
    }
	return 0;
}