记录编号	315590	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]从零开始的序列	最终得分	100
用户昵称	农场主	是否通过	通过
代码语言	C++	运行时间	0.080 s
提交时间	2016-10-05 16:46:42	内存使用	20.32 MiB

#include<cstdio>
#include<algorithm>
#define maxn 1000000
using namespace std;
int fa[maxn]={0};
int size[maxn]={0};
bool vis[maxn]={0};
int maxv[maxn]={0};
int n;
class poi{
public:
	int id,x;
}a[maxn];
void init(int n){
	for (int i=1;i<=n;i++){
		fa[i]=i;
		size[i]=1;
	}
}
int find(int x){
	if (fa[x]==x){
		return x;
	}
	else{
		int f=find(fa[x]);
		return fa[x]=f;
	}
}
void merge(int a,int b){
	int fa_a=find(a),fa_b=find(b);
	size[fa_a]+=size[fa_b];
	fa[fa_b]=fa_a;
}
bool cmp(poi a,poi b){
	return a.x>b.x;
}
void read(){
	scanf("%d",&n);
	init(n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i].x);
		a[i].id=i; 
	}
	sort(a+1,a+n+1,cmp);
	int tot=0;
	for (int i=1;i<=n;i++){
		int id=a[i].id;
		vis[id]=1;
		if (vis[a[i].id-1]){
			merge(id-1,id);
		}
		if (vis[id+1]){
			merge(id,id+1);
		}
		if (tot<size[find(id)]){
			for (int j=tot+1;j<=size[find(id)];j++){
				maxv[j]=a[i].x;
			}
			tot=size[find(id)];
		}
	}
	for (int i=1;i<=n;i++){
		printf("%d ",maxv[i]);
	}
}
int main(){
	freopen("sky_seq.in","r",stdin);
	freopen("sky_seq.out","w",stdout);
	read();
	return 0;
}