poj2823 Sliding Window luogu1886 滑动窗口 单调队列

模板题

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int l1=1, r1, l2=1, r2, q1[1000005], q2[1000005], a[1000005], n, k;
int ans1[1000005], ans2[1000005];
void rn(int &x){
	char ch=getchar();
	int f=1;
	while(ch<'0' || ch>'9'){
		if(ch=='-')	f = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
}
int main(){
	rn(n);rn(k);
	for(int i=1; i<=n; i++){
		while(l1<=r1 && q1[l1]<=i-k)	l1++;
		while(l2<=r2 && q2[l2]<=i-k)	l2++;
		rn(a[i]);
		while(l1<=r1 && a[q1[r1]]>a[i])	r1--;
		q1[++r1] = i;
		while(l2<=r2 && a[q2[r2]]<a[i])	r2--;
		q2[++r2] = i;
		ans1[i] = a[q1[l1]];
		ans2[i] = a[q2[l2]];
	}
	for(int i=k; i<=n; i++)	printf("%d ", ans1[i]);
	putchar('
');
	for(int i=k; i<=n; i++)	printf("%d ", ans2[i]);
	return 0;
}