题解：P10522 [XJTUPC2024] 雪中楼

Strange_qwq · 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;
}