/* 双链表 https://www.acwing.com/problem/content/829/
实现一个双链表，双链表初始为空，支持 5种操作：

在最左侧插入一个数；
在最右侧插入一个数；
将第 k个插入的数删除；
在第 k个插入的数左侧插入一个数；
在第 k个插入的数右侧插入一个数
现在要对该链表进行 M次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k个插入的数并不是指当前链表的第 k个数。例如操作过程中一共插入了 n个数，则按照插入的时间顺序，这 n
个数依次为：第 1个插入的数，第 2个插入的数，…第 n个插入的数。

输入格式
第一行包含整数 M，表示操作次数。

接下来 M行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 x。
R x，表示在链表的最右端插入数 x。
D k，表示将第 k个插入的数删除。
IL k x，表示在第 k个插入的数左侧插入一个数。
IR k x，表示在第 k个插入的数右侧插入一个数。
输出格式
共一行，将整个链表从左到右输出。

数据范围
1≤M≤100000

所有操作保证合法。

输入样例：
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2
输出样例：
8 7 7 3 2 9

题目解答：思路：

链表 不能够随机访问，但是如果用链式前项星建立链表，可以访问第k个结点，复杂度为0(1),
注意第k的结点前面一个结点的序号不是k-1 ，而是pre[k],后面一个结点的不是k+1，而是ne[k]
链表结点的顺序不是1-k，而是按照结点的插入的先后顺序 建立的。
本题双链表增加一个序号为0的结点，代表表头，增加一个序号为1的结点 代表 表尾。先建立结点0 与结点1的
ne 与pre的关系，所有的结点都插入到结点0 到结点1 之间，而且都是用的后插法。（表头为0，表尾为1）
例如插入到头部，相当于插入到 0 结点的后面， 插入到尾部，相当于插入的结点1的前面（也就是pre[1] 结点的后面）
所以可以统一写一个函数 插入到k 结点的后面。 本题的题目顺序 从1开始，但是我们标注其它结点顺序从2 开始，
所以插入结点的顺序标号需要+1.

*/

include[HTML_REMOVED]

using namespace std;
const int N=1e5+5;
//head 记录 表维结点，e[n],存储结点的值，ne 记录下一个结点的序号，pre 前面一个结点的序号，idx 新建结点编号
int e[N],ne[N],pre[N],idx; //本题目 表头为0 ，表尾为1
void insert(int k,int x)
{
e[idx]=x; //存储结点的值 ，然后开始修改结点的指针
//k的后面一个结点的序号 ne[k]
ne[idx]=ne[k];//第一条语句
pre[ne[k]]=idx;
ne[k]=idx;
pre[idx]=k;
idx;//下次需要 把结点序号 增加1,结点需要是1 2 3 4 从2开始的， 第一个真实结点为2， 0 1都是虚构。
}
//删掉结点k
void del(int k)
{
ne[pre[k]]=ne[k];
pre[ne[k]]=pre[k];
}
int m;
int main()
{
cin>>m;
//初始化 元素 ，新建结点0 与结点1 ，
ne[0]=1;
pre[1]=0;
idx=2;
while(m–)
{
string s; //1个字母 也用 字符串 不容易错，否则 空格，换行都是字符很容易错
cin>>s;
if(s==”R”) //最右端插入x,相当于 在pre[1]的后面插入一个x
{
int x;
cin>>x;
insert(pre[1],x);
}
else if(s==”D”)
{
int k;
cin>>k;
k;// 标号从2开始，题目从1开始，需要+1
del(k);
}
else if(s==”L”)
{
int x;//在最左端插入，相当于在结点标号0的后面插入
cin>>x;
insert(0,x); // 在0结点的后面插入一个结点x
}
else if(s==”IL”)
{
int k,x;
cin>>k>>x;
k=k+1;//我们从2开始，题目从1开始，整体+1
insert(pre[k],x);//在k的左边插入x，相当于在找到k的左边序号 pre[k+1]的右边插入x
}
else if(s==”IR”)
{
int k,x;
cin>>k>>x;
k=k+1;//我们从2开始，题目从1开始，整体+1
insert(k,x); //直接在k+1的右边插入 x
}
}
//遍历所以的元素 ,i!=1 结点1结束哦
for(int i=ne[0];i!=1;i=ne[i]) // 从0的下一个结点开始为真实我们插入的结点,最后一个结点的编号为1
{
int x=e[i];
cout<<x<<” “;
}
return 0;
}

```