题目
链接：https://ac.nowcoder.com/acm/contest/83391/A
来源：牛客网

给出一个长度为
𝑛
n 数组
𝑎
a，请你设计这样一种数据结构，需要支持以下两种操作共
𝑘
k 次：
- 1 x y：在元素
𝑥
x 后插入一个元素
𝑦
y。
- 2 x：删除元素
𝑥
x。
保证任意时刻数组当中不存在相同元素，并且对于操作中的
𝑥
x 保证一定存在。

请输出所有操作完成后的数组。
输入描述:
第一行包含两个整数
𝑛
,
𝑘
(
1
≤
𝑛
,
𝑘
≤
2
×
1
0
5
)
n,k(1≤n,k≤2×10
5
) 表示数组长度和操作次数。
第二行
𝑛
n 个整数
𝑎
𝑖
(
1
≤
𝑎
𝑖
≤
1
0
9
)
a
i
​
(1≤a
i
​
≤10
9
) 表示数组
𝑎
a。
接下来
𝑘
k 行，每行会有一个操作标号
1
1 或
2
2，对应题目中的操作
1
,
2
1,2，以及对应的
𝑥
,
𝑦
(
1
≤
𝑥
,
𝑦
≤
1
0
9
)
x,y(1≤x,y≤10
9
)。
输出描述:
一个数组
𝑎
a 表示所有操作完成后的数组，如果为空则输出也为空。
示例1
输入
复制
4 4
2 1 4 3
2 1
1 4 5
2 2
1 5 1
输出
复制
4 5 1 3
说明
样例1中，原始数组为 (2,1,4,3)。
第一次操作删除元素1，变为(2,4,3)。
第二次操作在元素4 后面添加元素 5，变为 (2,4,5,3)。
第三次操作删除元素 2，变为 (4,5,3)。
第四次操作在元素 5 后面添加元素 1，变为 (4,5,1,3)。
代码

include[HTML_REMOVED]

using namespace std;
const int N=4e5+10;//双链表 内存开两倍
map[HTML_REMOVED]mp;//存储元素与对应的idx
int n,k;
long long e[N],l[N],r[N],ne[N],idx;
void init()
{
r[0]=1;
l[1]=0;
idx=2;
}
void add(int k,long long x)
{
e[idx]=x;
l[idx]=k;
r[idx]=r[k];
l[r[k]]=idx;
r[k]=idx;
}
void move(int k)
{
l[r[k]]=l[k];
r[l[k]]=r[k];
}
int main()
{
init();
cin>>n>>k;
for(int i=1;i<=n;i)
{
long long x;
cin>>x;
mp[x]=idx;//x-idx
add(l[1],x);//都在1的左边插入元素
}
while(k–)
{
int num;
cin>>num;
if(num==1)
{
long long nn,mm;
cin>>nn>>mm;
mp[mm]=idx;
add(mp[nn],mm);//nn右边插入mm
}
else
{
long long nn;
cin>>nn;
move(mp[nn]);
}
}
for(int i=r[0];i!=1;i=r[i])
{
cout<<e[i]<<’ ‘;
}
return 0;
}