2485. [HZOI 2016]从零开始的序列

★★ 输入文件：sky_seq.in 输出文件：sky_seq.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

这个名字只是吸引你们这些死宅过来的。跟题目没关系。

现在Sky_miner给你一个序列，定义f(x)为(所有长度为x的区间中的最小值)的最大值.

要求输出f(1) .. f(n)

1 <= n <= 2*10^5

【输入格式】

第一行一个正整数n，含义如题

第二行共n个整数，为给定的序列，每一个整数 -10000 <= x <= 10000

【输出格式】

一行，共n个正整数，分别为f(1) f(2) .. f(n)

【样例输入】

3 4 1 3 9

【样例输出】

9 3 1 1 1

【来源】

HZOI 2016

分析：

大概有两种做法...

一种是比较直接的并查集做法...

就是我们把元素从大到小排序，依次加入序列中，然后并查集维护联通块的大小，更新答案，最后因为$f[i]>=f[i+1]$再$O(N)$更新一遍就好了...

一种是单调栈做法...

维护$l[i]r[i]$代表以$a[i]$为最小值所能扩展到最远的子序列，然后更新答案...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

using namespace std;

const int maxn=200000+5;

int n,a[maxn],f[maxn],fa[maxn],siz[maxn],pos[maxn],vis[maxn];

inline int read(void){

	char ch=getchar();int f=1,x=0;

	while(!(ch>='0'&&ch<='9')){

		if(ch=='-') f=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

	return f*x;

}

inline int find(int x){

	return fa[x]==x?x:fa[x]=find(fa[x]);

}

inline bool cmp(int x,int y){

	return a[x]>a[y];

}

signed main(void){

	freopen("sky_seq.in","r",stdin);

	freopen("sky_seq.out","w",stdout);

	n=read();memset(f,-1,sizeof(f));

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

		a[i]=read(),fa[i]=i,siz[i]=1,pos[i]=i;

	sort(pos+1,pos+n+1,cmp);

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

		vis[pos[i]]=1;

		if(pos[i]>1&&vis[pos[i]-1]){

			int fx=find(pos[i]-1);

			siz[pos[i]]+=siz[fx],fa[fx]=pos[i];

		}

		if(pos[i]<n&&vis[pos[i]+1]){

			int fx=find(pos[i]+1);

			siz[pos[i]]+=siz[fx],fa[fx]=pos[i];

		}

		if(f[siz[pos[i]]]==-1)

			f[siz[pos[i]]]=a[pos[i]];

	}

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

		f[i]=max(f[i],f[i+1]);

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

		printf("%d ",f[i]);puts("");

	fclose(stdin);fclose(stdout);

	return 0;

}

By NeighThorn

序列

COGS 2485. [HZOI 2016]从零开始的序列