103444: [Atcoder]ABC344 E - Insert or Erase
Description
Score: $475$ points
Problem Statement
You are given a sequence $A=(A_1,\ldots,A_N)$ of length $N$. The elements of $A$ are distinct.
Process $Q$ queries in the order they are given. Each query is of one of the following two types:
1 x y
: Insert $y$ immediately after the element $x$ in $A$. It is guaranteed that $x$ exists in $A$ when this query is given.2 x
: Remove the element $x$ from $A$. It is guaranteed that $x$ exists in $A$ when this query is given.
It is guaranteed that after processing each query, $A$ will not be empty, and its elements will be distinct.
Print $A$ after processing all the queries.
Constraints
- $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$
- For queries of the first type, $1 \leq x,y \leq 10^9$.
- When a query of the first type is given, $x$ exists in $A$.
- For queries of the second type, $1 \leq x \leq 10^9$.
- When a query of the second type is given, $x$ exists in $A$.
- After processing each query, $A$ is not empty, and its elements are distinct.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $\ldots$ $A_N$ $Q$ $\mathrm{Query}_1$ $\vdots$ $\mathrm{Query}_Q$
Here, $\mathrm{Query}_i$ represents the $i$-th query and is given in one of the following formats:
$1$ $x$ $y$
$2$ $x$
Output
Let $A=(A_1,\ldots,A_K)$ be the sequence after processing all the queries. Print $A_1,\ldots,A_K$ in this order, separated by spaces.
Sample Input 1
4 2 1 4 3 4 2 1 1 4 5 2 2 1 5 1
Sample Output 1
4 5 1 3
The queries are processed as follows:
- Initially, $A=(2,1,4,3)$.
- The first query removes $1$, making $A=(2,4,3)$.
- The second query inserts $5$ immediately after $4$, making $A=(2,4,5,3)$.
- The third query removes $2$, making $A=(4,5,3)$.
- The fourth query inserts $1$ immediately after $5$, making $A=(4,5,1,3)$.
Sample Input 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
Sample Output 2
5 1 7 2 3
Input
Output
问题描述
你被给定一个长度为$N$的序列$A=(A_1,\ldots,A_N)$。$A$的元素各不相同。
按给定的顺序处理$Q$个查询。每个查询有以下两种类型之一:
1 x y
:在$A$中元素$x$之后立即插入$y$。当给出这个查询时,可以保证$x$存在于$A$中。2 x
:从$A$中删除元素$x$。当给出这个查询时,可以保证$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$个查询,给出以下格式之一:
$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)$。
- 第二个查询在$4$之后立即插入$5$,使得$A=(2,4,5,3)$。
- 第三个查询删除$2$,使得$A=(4,5,3)$。
- 第四个查询在$5$之后立即插入$1$,使得$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