AT_abc217_e [ABC217E] Sorting Queries

题目描述

有一个空的序列 $A$。现在有 $Q$ 个操作，请按给定的顺序依次处理这些操作。
操作有以下三种类型之一：

• 1 x ：将 $x$ 添加到 $A$ 的末尾。
• 2 ：输出 $A$ 的第一个元素，然后将其从 $A$ 中删除。保证当出现该操作时，$A$ 不为空。
• 3 ：将 $A$ 按升序排序。

输入格式

输入从标准输入中给出，格式如下：

$Q$
$\mathrm{query}\ 1$
$\mathrm{query}\ 2$
$\vdots$
$\mathrm{query}\ Q$

第 $i$ 个操作 $\mathrm{query}\ i$，首先给出操作类型 $c_i$（$1$、$2$ 或 $3$ 之一）。如果 $c_i = 1$，则还会给出一个整数 $x$。

也就是说，每个操作有以下三种格式之一：

$1\ x$

$2$

$3$

输出格式

设操作类型为 $2$ 的操作总共有 $q$ 次，请输出 $q$ 行。
第 $j$ 行（$1 \leq j \leq q$）输出第 $j$ 次此类操作的答案。

输入输出样例 #1

输入 #1

8
1 4
1 3
1 2
1 1
3
2
1 0
2

输出 #1

1
2

输入输出样例 #2

输入 #2

9
1 5
1 5
1 3
2
3
2
1 6
3
2

输出 #2

5
3
5

说明/提示

限制条件

• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x \leq 10^9$
• 当出现操作 $2$ 时，$A$ 保证非空。
• 输入均为整数。

样例解释 1

在输入样例 $1$ 中，处理完第 $i$ 个操作后，$A$ 的状态如下所示：

• $(4)$
• $(4,\ 3)$
• $(4,\ 3,\ 2)$
• $(4,\ 3,\ 2,\ 1)$
• $(1,\ 2,\ 3,\ 4)$
• $(2,\ 3,\ 4)$
• $(2,\ 3,\ 4,\ 0)$
• $(3,\ 4,\ 0)$

样例解释 2

在输入样例 $2$ 中，处理完第 $i$ 个操作后，$A$ 的状态如下所示：

• $(5)$
• $(5,\ 5)$
• $(5,\ 5,\ 3)$
• $(5,\ 3)$
• $(3,\ 5)$
• $(5)$
• $(5,\ 6)$
• $(5,\ 6)$
• $(6)$

由 ChatGPT 4.1 翻译