【题目来源】
https://www.luogu.com.cn/problem/P1160
【题目描述】
一个学校里老师要将班上 N 个同学排成一列，同学被编号为 1∼N，他采取如下的方法：
（1）先将 1 号同学安排进队列，这时队列中只有他一个人；
（2）2∼N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；
（3）从队列中去掉 M 个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
【输入格式】
第一行一个整数 N，表示了有 N 个同学。
第 2∼N 行，第 i 行包含两个整数 k，p，其中 k 为小于 i 的正整数，p 为 0 或者 1。若 p 为 0，则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边。
第 N+1 行为一个整数 M，表示去掉的同学数目。
接下来 M 行，每行一个正整数 x，表示将 x 号同学从队列中移去，如果 x 号同学已经不在队列中则忽略这一条指令。
【输出格式】
一行，包含最多 N 个空格隔开的整数，表示了队列从左到右所有同学的编号。
【输入样例】
4
1 0
2 1
1 0
2
3
3
【输出样例】
2 4 1
【数据范围】
对于 20% 的数据，1≤N≤10。
对于 40% 的数据，1≤N≤1000。
对于 100% 的数据，1<M≤N≤10^5。
【算法分析】
● 本题利用数组模拟实现双链表的代码思想，与“AcWing 827：双链表”的思想基本一致。详见：https://blog.csdn.net/hnjzsyjyj/article/details/150845789
● 本题利用数组模拟实现双链表的示意图，附设了 idx=0 及 idx=1 两个结点。之后，插入结点 2（idx=2）的示意图如下所示。
● 特别要注意，本题在删除某个结点时，要进行特判，看看待删结点是否还存在。若不存在，忽略此删除操作。
● 本题用STL list实现的代码，详见：https://blog.csdn.net/hnjzsyjyj/article/details/151970421
【算法代码】
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int le[maxn],ri[maxn],v[maxn],idx; bool st[maxn]; int n,m,k,q,x; void init() { ri[0]=1,le[1]=0; idx=2; } void insert(int p,int x) { v[idx]=x; le[idx]=p,ri[idx]=ri[p]; le[ri[p]]=idx,ri[p]=idx++; } void remove(int k) { ri[le[k]]=ri[k]; le[ri[k]]=le[k]; } int main() { init(); insert(0,1); cin>>n; for(int i=2; i<=n; i++) { cin>>k>>q; if(q) insert(k+1,i); else insert(le[k+1],i); } cin>>m; while(m--) { cin>>x; if(!st[x]) { remove(x+1); st[x]=true; } } for(int i=ri[0]; i!=1; i=ri[i]) { cout<<v[i]<<" "; } return 0; } /* in: 4 1 0 2 1 1 0 2 3 3 out: 2 4 1 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/150845789
https://blog.csdn.net/hnjzsyjyj/article/details/151970421
https://www.luogu.com.cn/problem/solution/P1160
https://blog.csdn.net/lq1990717/article/details/127429719
