题解：P10522 [XJTUPC2024] 雪中楼

sillation · 2024-05-22 22:56:49 · 题解

题目传送门

因为需插入的元素较多，1 \le n \le 2 \times 10^{5}。所以考虑用链表，边读边插入。最后翻转就行。

考虑用 C++ 的 STL 库。 支持以下操作：

• list<int> a，定义一个 int 类型的链表 a。在本题中可以建立一个 int 类型的链表 s。

• list<int>::iterator it，定义一个 int 类型名为 it 的迭代器。在本题中可以建立一个 int 类型的迭代器数组 a。

• insert(it,x)，在迭送器 it 所在的元素的前面插入元素 x。

• a.begin(),a.end()，链表开始和末尾的迭送器指针。

• s.pop()_front，删除链表开头。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
list<int> s;
list<int>::iterator a[N]={s.begin(),s.end()};//初始化 
int x;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i]=s.insert(a[x],i);
    }
    reverse(s.begin(),s.end());//反转
    while(!s.empty()){
        cout<<s.front()<<" ";
        s.pop_front();
    }
    return 0;
}