D2 - 单调队列

int val[maxn];

template< class Comp >
class monoque {
	int ar[maxn] {};
	int head = 0, end = 0;
	Comp cmp;
public:
	int front() { return ar[head]; }
	void pop() { ++head; }
	bool empty() { return head == end; }
	int back() { return ar[end - 1]; }
	int len() { return back() - front() + 1; }	// 原数列
	int push(int x) {
		while (!empty() && !cmp(val[back()], val[x])) --end;
		ar[end++] = x;
		return val[front()];
	}
};

template< class Comp >
inline void slide(int n, int k, monoque<Comp> &mque) {
	static int head;
	for (int i = 0; i < k; i++) head = mque.push(i);
	printf("%d", head);
	for (int i = k; i < n; i++) {
		if (mque.len() == k) mque.pop();
		printf(" %d", mque.push(i));
	}
	putchar(10);
}