題目描述

一個學校里老師要將班上?N?個同學排成一列，同學被編號為 1～N，他采取如下的方法：

1. 先將?11?號同學安排進隊列，這時隊列中只有他一個人；

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

說明/提示

【樣例解釋】

將同學?2?插入至同學?1?左邊，此時隊列為：

2 1

將同學?3?插入至同學?2?右邊，此時隊列為：

2 3 1

將同學?4?插入至同學?1?左邊，此時隊列為：

2 3 4 1

將同學?3?從隊列中移出，此時隊列為：

2 4 1

同學?3?已經不在隊列中，忽略最后一條指令

最終隊列：

2 4 1

【數據范圍】

對于 20%?的數據，1≤N≤10。

對于 40%?的數據，1≤N≤1000。

對于 100%?的數據，1<M≤N≤105。

用結構體模擬鏈表

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=1e9+7;
const int M=4e4+10;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int minn=0x3f3f3f3f;
int maxn=0xc0c0c0c0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,k,p;
string s;
struct P{int l,r,del;
}a[N];
void solve()
{cin>>n;a[0].l=1,a[0].r=1;a[1].l=0,a[1].r=0;for(int i=2;i<=n;i++){cin>>k>>p;if(p){a[i].l=k;a[i].r=a[k].r;a[a[k].r].l=i;a[k].r=i;}else{a[i].r=k;a[i].l=a[k].l;a[a[k].l].r=i;a[k].l=i;}}cin>>m;while(m--){int x;cin>>x;a[x].del=1;}for(int i=a[0].r;i;i=a[i].r)if(!a[i].del) cout<<i<<" ";cout<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
//	cin>>t;while(t--){	solve();}return 0;
}

用list

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=1e9+7;
const int M=4e4+10;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int minn=0x3f3f3f3f;
int maxn=0xc0c0c0c0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,k,p;
string s;
list<int>::iterator pos[N];
list<int> l;
bool vis[N];
void solve()
{cin>>n;l.push_front(1);pos[1]=l.begin();for(int i=2;i<=n;i++){cin>>k>>p;if(!p)pos[i]=l.insert(pos[k],i);else{auto nextt=next(pos[k]);pos[i]=l.insert(nextt,i);}}cin>>m;while(m--){int x;cin>>x;if(!vis[x])l.erase(pos[x]);vis[x]=true;}for(int x:l)cout<<x<<" ";cout<<endl; 
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
//	cin>>t;while(t--){	solve();}return 0;
}