PKU 2823 - Sliding Window

問題文 : Sliding Window

解法 :

見た感じセグメント木でもよさそうだが, 蟻本でdequeを使うO(N) 解法が紹介されていたので, dequeの練習がてら書いてみた. dequeステキ, 便利.
やはり書くと分かりやすい.

dqでは, i < j かつ a[i] < a[j] となるようにdequeにデータを詰めていく.
dq2では, i < j かつ a[i] > a[j] となるようにdequeにデータを詰めていく.

使い終わりのときには先頭に来ている(もしくは捨てられている) ので, 除去は O(1) で実現できる.

コード :

#include <cstdio>
#include <deque>
#include <algorithm>

using namespace std;

int a[1000000];
int x[1000000], y[1000000];
deque<int> dq, dq2;

int main()
{
	int n, k;
	scanf("%d %d", &n, &k);
	
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	
	for (int i = 0; i < k - 1; i++){
		while (dq.size() && a[dq[dq.size() - 1]] >= a[i]) dq.pop_back();
		dq.push_back(i);
		
		while (dq2.size() && a[dq2[dq2.size() - 1]] <= a[i]) dq2.pop_back();
		dq2.push_back(i);
	}
	
	for (int i = 0, j; (j = i + k - 1) < n; i++){
		while (dq.size() && a[dq[dq.size() - 1]] >= a[j]) dq.pop_back();
		dq.push_back(j);
		while (dq2.size() && a[dq2[dq2.size() - 1]] <= a[j]) dq2.pop_back();
		dq2.push_back(j);
		
		x[i] = a[dq[0]];
		y[i] = a[dq2[0]];
		if (dq[0] == i) dq.pop_front();
		if (dq2[0] == i) dq2.pop_front();
	}
	
	for (int i = 0; i <= n - k; i++) printf("%d%c", x[i], i == n - k ? '\n' : ' ');
	for (int i = 0; i <= n - k; i++) printf("%d%c", y[i], i == n - k ? '\n' : ' ');
	return (0);
}