题目链接

单调队列模板题，求 n 个数每 k 个连续的数的最小最大值；最大值可直接插相反数进去，取出的时候再取回即可。

poj 上 STL 特别的慢了，语言要选 C++而非 G++才能勉强跑过…大致能看个做法即可。

#include <cstdio>
#include <deque>
using namespace std;
const int N = 1e6 + 9;
typedef int ll;
typedef pair<ll, int> pli;
struct Monotone : deque<pli>
{
	void push(const pli &p, int k)
	{
		while (!empty() && back().first >= p.first)
			pop_back();
		for (push_back(p); p.second - front().second >= k;)
			pop_front();
	}
} q[2];
int n, k, ans[2][N];
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0, a; i < n; ++i)
	{
		scanf("%d", &a);
		q[0].push(pli(a, i), k);
		ans[0][i] = q[0].front().first;
		q[1].push(pli(-a, i), k);
		ans[1][i] = -q[1].front().first;
	}
	for (int j = 0; j < 2; ++j)
		for (int i = k - 1; i < n; ++i)
			printf("%d%c", ans[j][i], i + 1 == n ? '\n' : ' ');
}

用数组模拟 STL 队列后直接快了一倍多…

#include <cstdio>
#include <deque>
using namespace std;
const int N = 1e6 + 9;
typedef int ll;
typedef pair<ll, int> pli;
template <typename pli, size_t N>
struct WuKQueue
{
	pli q[N];
	int b, e;
	WuKQueue() : b(0), e(0) {}
	bool empty() const { return b == e; }
	pli back() const { return q[e - 1]; }
	pli front() const { return q[b]; }
	void pop_front() { ++b; }
	void pop_back() { --e; }
	void push_back(pli p) { q[e++] = p; }
};
struct Monotone : WuKQueue<pli, N>
{
	void push(const pli &p, int k)
	{
		while (!empty() && back().first >= p.first)
			pop_back();
		for (push_back(p); p.second - front().second >= k;)
			pop_front();
	}
} q[2];
int n, k, ans[2][N];
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0, a; i < n; ++i)
	{
		scanf("%d", &a);
		q[0].push(pli(a, i), k);
		ans[0][i] = q[0].front().first;
		q[1].push(pli(-a, i), k);
		ans[1][i] = -q[1].front().first;
	}
	for (int j = 0; j < 2; ++j)
		for (int i = k - 1; i < n; ++i)
			printf("%d%c", ans[j][i], i + 1 == n ? '\n' : ' ');
}