#include <cstdio>
#include <deque>
using namespace std;
const int MAXN=1000001;
struct Node
{
	int d,i;	
};

int d1,d2[MAXN],n,m,num[MAXN];//d1 min d2 max

int main()
{
	scanf("%d%d",&n,&m);
	deque<Node> q1,q2;
	for(int i=0;i<n;i++)
	{
		int x;
		scanf("%d",&x);
		Node now={x,i};
		while (!q1.empty()&&i-q1.front().i>=m) 
			q1.pop_front();
		while (!q2.empty()&&i-q2.front().i>=m)
			q2.pop_front();
		if (q1.empty())
		{
			q1.push_back(now);
			d1=x;
		}
		else
		{
			Node temp=q1.front();
			d1=min(now.d,temp.d);
			while (!q1.empty()&&q1.back().d>now.d) q1.pop_back();
			q1.push_back(now);
		}
		if (i>=m-1)
		{
			if (i>m-1)printf(" ");
			printf("%d",d1);
		}
		//////////
		if (q2.empty())
		{
			q2.push_back(now);
			d2[i]=x;
		}
		else
		{
			Node temp=q2.front();
			d2[i]=max(now.d,temp.d);
			while (!q2.empty()&&q2.back().d<now.d) q2.pop_back();
			q2.push_back(now);
		}
	}
	printf("\n");
	printf("%d",d2[m-1]);
	for(int i=m;i<n;i++)
		printf(" %d",d2[i]);
	printf("\n");
	return 0;
}

• Re:为什么O（n）的单调队列也TLE???麻烦大家看一下 (8) hustzhangyt 2010-07-20 15:02:40