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('\n');

	for(int i=k; i<=n; i++)	printf("%d ", ans2[i]);

	return 0;

}

巴特西

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

最新文章

热门文章

巴特西

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

最新文章

热门文章

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