Insert or Erase

题目描述

你被给定一个长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$。$A$ 的元素互不相同。 按给定顺序处理 $Q$ 个查询。每个查询为以下两种类型之一：

$1 x y$ ：在序列 $A$ 中元素 $x$ 的后面立即插入 $y$。保证在该查询给出时 $x$ 存在于 $A$。 $2 x$ ：将元素 $x$ 从 $A$ 中删除。保证在该查询给出时 $x$ 存在于 $A$。

保证在处理每个查询之后，$A$ 不会为空，且其元素互不相同。 在处理完所有查询后输出 $A$。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $\ldots$ $A_N$ $Q$ $\mathrm{Query}_1$ $\vdots$ $\mathrm{Query}_Q$

其中，$\mathrm{Query}_i$ 表示第 $i$ 个查询，格式为以下之一： $1$ $x$ $y$

$2$ $x$

输出格式

令 $A=(A_1,\ldots,A_K)$ 为处理完所有查询后的序列。按该顺序输出 $A_1,\ldots,A_K$，用空格分隔。

4
2 1 4 3
4
2 1
1 4 5
2 2
1 5 1

4 5 1 3

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

5 1 7 2 3

提示

$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$ 不为空，且其元素互不相同。 所有输入值均为整数。查询按如下方式处理：

最初，$A=(2,1,4,3)$。 第一个查询删除了 $1$，得到 $A=(2,4,3)$。 第二个查询在 $4$ 的后面插入了 $5$，得到 $A=(2,4,5,3)$。 第三个查询删除了 $2$，得到 $A=(4,5,3)$。 第四个查询在 $5$ 的后面插入了 $1$，得到 $A=(4,5,1,3)$。

标签: AtCoder|abc344E

来源

AtCoder|abc344E