题解：P10522 [XJTUPC2024] 雪中楼

abc1856896 · 2024-05-22 11:11:33 · 题解

solution

由于每次插入 a_i 要用到的插入操作极多，那么考虑维护链表。

每次插入一个 a_i，若 i 不是 0，那么就把 i 插入到链表 a_i 的左边即可。

最后再翻转即可。

code

#include<bits/stdc++.h>
using namespace std;
int n;
list<int> st;

void solve(){
    list<int>::iterator a[200005]={st.begin(),st.begin()};
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[i]=st.insert(a[x],i);
    }
    reverse(st.begin(),st.end());
    for(auto i:st){
        cout<<i<<" ";
    }   
}
int main() {
    solve();
    return 0;
}