自动搬运

查看原文

来自洛谷，原作者为

	Strange_qwq lazy

搬运于2025-08-24 22:58:50，当前版本为作者最后更新于2024-05-22 19:46:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

每次输入一个 $a_i$ 如果 $i=0$ 就插入到链表尾部，否则插入到 $a_i$ 左边，最后再翻转即可。

因为既然左边的房子都已经构造好了。那么右边的房子不影响左边的答案，因此可以增量构造。考虑 $i$ 在答案序列插入到 $a_i$ 后面就是恰好比 $a_i$ 高。

code

#include <bits/stdc++.h>
#using namespace std;
int f[200005];
int g(int u){
	if(f[u]==u){
		return u;
	}
	return f[u]=g(f[u]);
}
int a[200005];
int next[200005];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=n;++i){
		f[i]=i;
	}
	for(int i=n;i;--i){
		int x=g(a[i]);
		next[x]=i;
		f[x]=i;
	}
	int k=n;
	while(a[k]!=0) --k;
	while(k){
		printf("%d ",k);
		k=next[k];
	}
	return 0;
}