分数: 475 点
问题陈述
给你一个序列 A=(A_1,\ldots,A_N) 长度 N。的要素 A 是不同的。
流程 Q 按给出的顺序进行查询。每个查询属于以下两种类型之一:
1 x y:插入 y 紧接在元素之后 x in A。可以保证 x 存在于 A 给出此查询时。2 x:删除元素 x 来自 A。可以保证 x 存在于 A 给出此查询时。
保证在处理每个查询后, A 不会为空,并且其元素将是不同的。
打印 A 处理完所有查询后。
约束
- 1 \leq N \leq 2\times 10^5
- 1 \leq Q \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- A_i \neq A_j
- 对于第一类查询, 1 \leq x,y \leq 10^9.
- 当给出第一类型的查询时, x 存在于 A.
- 对于第二种类型的查询, 1 \leq x \leq 10^9.
- 当给出第二类型的查询时, x 存在于 A.
- 处理每个查询后, A 不为空,并且其元素是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_1 \ldots A_N
Q
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q
在这里, \mathrm{Query}_i 代表 i-th 查询并以下列格式之一给出:
1 x y
2 x
输出
让 A=(A_1,\ldots,A_K) 是处理所有查询后的序列。打印 A_1,\ldots,A_K 按此顺序,用空格分隔。
示例输入 1
4 2 1 4 3 4 2 1 1 4 5 2 2 1 5 1
示例输出 1
4 5 1 3
查询处理如下:
- 最初, A=(2,1,4,3).
- 第一个查询删除 1, 制作 A=(2,4,3).
- 第二个查询插入 5 紧接着 4, 制作 A=(2,4,5,3).
- 第三个查询删除 2, 制作 A=(4,5,3).
- 第四个查询插入 1 紧接着 5, 制作 A=(4,5,1,3).
示例输入 2
6 3 1 4 5 9 2 7 2 5 1 3 5 1 9 7 2 9 2 3 1 2 3 2 4
示例输出 2
5 1 7 2 3