← 返回题目列表

AtCoder · abc344_e

H. 插入或删除

中文机器翻译题面 查看原题

分数: 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