单调队列

呃呃

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
deque < int > dq;
int a[maxn];
int n, m;
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		while (!dq.empty() && a[dq.back()] > a[i])
			dq.pop_back();
		dq.push_back(i);
		if (i >= m) {
			while (!dq.empty() && dq.front() <= i - m)
				dq.pop_front();
			printf("%d ", a[dq.front()]);
		}
	}
	printf("\n");
	while (!dq.empty()) 
		dq.pop_front();
	for (int i = 1; i <= n; i++) {
		while (!dq.empty() && a[dq.back()] < a[i])
			dq.pop_back();
		dq.push_back(i);
		if (i >= m) {
			while (!dq.empty() && dq.front() <= i - m)
				dq.pop_front();
			printf("%d ", a[dq.front()]);
		}
	}
	printf("\n");
	return 0;
}