AT_abc294_d [ABC294D] Bank

题目描述

银行里有编号为 $1, 2, \dots, N$ 的人排队。
接下来会发生 $Q$ 个事件。每个事件属于以下三种之一：

• 1：在尚未被叫号的人中，编号最小的人被叫到前台。
• 2\ x：编号为 $x$ 的人第一次前往前台。（此时，$x$ 已经被叫号至少一次。）
• 3：在已经被叫号但还未前往前台的人中，编号最小的人再次被叫到前台。

请按被叫到前台的顺序，输出每次第 $3$ 种事件中被叫到前台的人的编号。

输入格式

输入以如下格式从标准输入读入。这里 $\text{event}_i$ 表示第 $i$ 个事件。

$N\ Q$
$\text{event}_1$
$\text{event}_2$
$\vdots$
$\text{event}_Q$

每个事件的输入格式如下三种之一：

1

2\ x

3

输出格式

设输入中第 $3$ 种事件的总数为 $X$，请输出 $X$ 行。
第 $i$ 行输出第 $i$ 次第 $3$ 种事件中被叫到前台的人的编号。

输入输出样例 #1

输入 #1

4 10
1
1
3
2 1
1
2 3
3
1
2 2
3

输出 #1

1
2
4

说明/提示

限制条件

• $1 \leq N \leq 5 \times 10^5$
• $2 \leq Q \leq 5 \times 10^5$
• 当所有人都已被叫号时，不会发生第 $1$ 种事件
• 对于第 $2$ 种事件，编号为 $x$ 的人已经被叫号至少一次
• 对于第 $2$ 种事件，编号为 $x$ 的人不会前往前台超过一次
• 当所有被叫号的人都已前往前台时，不会发生第 $3$ 种事件
• 第 $3$ 种事件至少会发生一次
• 输入的所有值均为整数

样例解释 1

对于 $i=1,2,\dots,Q$，在第 $i$ 个事件发生前，已经被叫号但还未前往前台的人的集合如下：

• $i=1$：$\lbrace\ \rbrace$
• $i=2$：$\lbrace\ 1\rbrace$
• $i=3$：$\lbrace\ 1,2\rbrace$
• $i=4$：$\lbrace\ 1,2\rbrace$
• $i=5$：$\lbrace\ 2\rbrace$
• $i=6$：$\lbrace\ 2,3\rbrace$
• $i=7$：$\lbrace\ 2\rbrace$
• $i=8$：$\lbrace\ 2\rbrace$
• $i=9$：$\lbrace\ 2,4\rbrace$
• $i=10$：$\lbrace\ 4\rbrace$

第 $3$ 种事件在 $i=3,7,10$ 时发生，因此此时集合中编号最小的人分别为 $1, 2, 4$，应依次输出。

由 ChatGPT 4.1 翻译