bzoj 3401: [Usaco2009 Mar]Look Up 仰望【单调栈】

用单调递减的栈从后往前扫一遍即可

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1000005;

int n,s[N],top,a[N],ans[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

int main()

{

	n=read();

	for(int i=1;i<=n;i++)

		a[i]=read();

	for(int i=n;i>=1;i--)

	{

		while(top&&a[s[top]]<=a[i])

			top--;

		ans[i]=s[top];

		s[++top]=i;

	}

	for(int i=1;i<=n;i++)

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

bzoj 3401: [Usaco2009 Mar]Look Up 仰望【单调栈】

最新文章

热门文章