題目
一個學校里老師要將班上N個同學排成一列，同學被編號為1～N，他采取如下的方法：
-
先將1號同學安排進隊列，這時隊列中只有他一個人；
-
2～N號同學依次入列，編號為i的同學入列方式為：老師指定編號為i的同學站在編號為1～(i?1)中某位同學（即之前已經入列的同學）的左邊或右邊；
-
從隊列中去掉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補充知識
鏈表的使用，可以完成以下的操作，實現一個數據結構，維護一張表（最初只有一個元素1）。支持以下的操作，其中x,y都是int范圍內的正整數，且都不一樣。
（1）ins_back(x,y)：將元素y插入到x后面
（2）ins_front(x,y)：將元素y插入到x前面
（3）ask_back(x)：詢問x后面的元素
（4）ask_front(x)：詢問x前面的元素
（5）del(x)：從表中刪除元素x，不改變其他元素的先后順序
struct node{int pre,nxt;//分別記錄前驅和后繼結點在數組s中的下標int key;node(int _key=0,int _pre=0,int _nxt=0){pre=_pre;nxt=_nxt;key=_key;}
};
node s[100005];
//一個池，以后想要新建一個結點，就從s數組里面拿出一個位置給新結點
//也可以使用指針new,delete實現
int tot=0;//記錄s數組目前使用了多少個位置，那么下一個可用的位置就是s[tot+1]
int find(int x){//查找x的結點編號，需要遍歷整個鏈表int now=1;while(now&&s[now].key!=x){now=s[now].nxt;return now;}
}
void ins_back(int x,int y){//y插在x后面 int now=find(x);s[++tot]=node(y,now,s[now].nxt);s[s[now].nxt].pre=tot;s[now].nxt=tot;
}
void ins_front(int x,int y){//y插在x前面 int now=find(x);s[++tot]=node(y,s[now].pre,now);s[s[now].pre].nxt=tot;s[now].pre=tot;
}
int ask_back(int x){int now=find(x);return s[s[now].nxt].key;
}
int ask_front(int x){int now=find(x);return s[s[now].pre].key;
}
void del(int x){int now=find(x);int le=s[now].pre,rt=s[now].nxt;s[le].nxt=rt;s[rt].pre=le;
}當然STL庫也提供了鏈表的相關操作，需要使用list的頭文件。支持以下的常用方法。
（1）list<int> a：定義一個int類型的鏈表a
（2）int arr[5]={1,2,3};lsit<int> a(arr,arr+3)：從數組arr中的前三個元素作為鏈表a的初始值
（3）a.size()：返回鏈表的結點數量
（4）list<int>::iterator it：定義一個名為it的迭代器（指針）
（5）a.begin();a.end()：鏈表開始和末尾的迭代器指針
（6）it++;it--：迭代器指向前一個和后一個元素
（7）a.push_front(x);a.push_back()：在鏈表開頭或者末尾插入元素x
（8）a.insert(it,x)：在迭代器it的前插入元素x
（9）a.pop_front();a.pop_back()：刪除鏈表開頭或者末尾
（10）a.erase(it)：刪除迭代器it所在的元素
（11）for(it=a.begin();it!=a.end();it++)：遍歷鏈表
解析
此題目利用一個雙向鏈表維護這個隊伍，每個同學記錄自己左邊和右邊的同學。這樣各種操作都可以的復雜度完成。可以使用上面的鏈表模板，但是需要稍微修改一下插入函數和刪除函數。使用數組index定位某位同學的結點編號，在插入和刪除時直接找到這位同學的結點編號，在插入時還要記錄下這名同學的結點編號。這樣就不需要每次都要遍歷整個鏈表了。
#include<iostream>
using namespace std;
struct node{int pre,nxt,key;node(int _key=0,int _pre=0,int _nxt=0){pre=_pre;nxt=_nxt;key=_key;}
};
node s[100005];
int n,m,tot=0,index[100005]={0};//記錄每個位置的結點編號
void ins_back(int x,int y){int now=index[x];//查找索引s[++tot]=node(y,now,s[now].nxt);s[s[now].nxt].pre=tot;s[now].nxt=tot;index[y]=tot;//記錄索引
}
void ins_front(int x,int y){int now=index[x];s[++tot]=node(y,s[now].pre,now);s[s[now].pre].nxt=tot;s[now].pre=tot;index[y]=tot;
}
void del(int x){int now=index[x];int le=s[now].pre,rt=s[now].nxt;s[le].nxt=rt;s[rt].pre=le;index[x]=0;
}
int main(){int x,k,p,now;cin>>n;s[0]=node();//令0恒為最左邊的結點ins_back(0,1);for(int i=2;i<=n;i++){cin>>k>>p;p ? ins_back(k,i):ins_front(k,i);}cin>>m;for(int i=1;i<=m;i++){cin>>x;if(index[x]){del(x);}}now=s[0].nxt;while(now){cout<<s[now].key<<" ";now=s[now].nxt;}return 0;
}
