AT_abc344_e [ABC344E] Insert or Erase

题目描述

给定一个长度为 $N$ 的数列 $A=(A_1,\ldots,A_N)$。$A$ 的各个元素互不相同。

接下来有 $Q$ 个操作，请按顺序依次处理。每个操作有以下两种类型之一：

• 1 x y ：在 $A$ 中元素 $x$ 的后面插入 $y$。保证在该操作时，$A$ 中一定存在 $x$。
• 2 x ：从 $A$ 中删除元素 $x$。保证在该操作时，$A$ 中一定存在 $x$。

保证每次操作后，$A$ 都非空且所有元素互不相同。

请输出所有操作处理完后的数列 $A$。

输入格式

输入以如下格式从标准输入给出。

$N$ $A_1$ $A_2$ $\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$。

输入输出样例 #1

输入 #1

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

输出 #1

4 5 1 3

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $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 种操作，$1 \leq x,y \leq 10^9$，且操作时 $A$ 中一定存在 $x$
• 对于第 2 种操作，$1 \leq x \leq 10^9$，且操作时 $A$ 中一定存在 $x$
• 每次操作后，$A$ 都非空且所有元素互不相同
• 输入均为整数

样例说明 1

操作依次如下：

• 初始 $A=(2,1,4,3)$。
• 第 1 次操作删除 $1$，$A=(2,4,3)$。
• 第 2 次操作在 $4$ 后插入 $5$，$A=(2,4,5,3)$。
• 第 3 次操作删除 $2$，$A=(4,5,3)$。
• 第 4 次操作在 $5$ 后插入 $1$，$A=(4,5,1,3)$。

由 ChatGPT 4.1 翻译