Bank

题目描述

$N$ 个人，ID 编号为 $1$、$2$、$\dots$、$N$，正在银行前排队。
将会发生 $Q$ 个事件。可以发生以下三种事件。

$1$ ：出纳员叫尚未被叫到的最小 ID 编号的人。 $2 x$ ：编号为 $x$ 的人在第一次来到出纳台。（在这里，编号为 $x$ 的人至少已经被出纳员叫过一次。） $3$ ：出纳员再次叫已经被叫过但尚未来过的人中 ID 编号最小的人。

在第三种事件中，打印被出纳员叫到的人的 ID 编号。

输入格式

输入按下列格式从标准输入给出，其中 $\text{event}_i$ 表示第 $i$ 个事件： $N$ $Q$ $\text{event}_1$ $\text{event}_2$ $\vdots$ $\text{event}_Q$

每个事件的描述为以下格式之一： 1

2 $x$

3

输出格式

输出 $X$ 行，其中 $X$ 是第三种事件的个数。
第 $i$ 行应包含在第 $i$ 次第三种事件中被叫到的人的 ID 编号。

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

1
2
4

提示

$1 \leq N \leq 5 \times 10^5$ $2 \leq Q \leq 5 \times 10^5$ 当所有人都至少已经被叫过一次时，不会出现第一种事件。 对于每个第二种事件，编号为 $x$ 的人至少已经被出纳员叫过一次。 对于每个第二种事件，编号为 $x$ 的人不会多次来到出纳台。 当所有已经被叫过的人都已来到出纳台时，不会出现第三种事件。 至少存在一次第三种事件。 输入中的所有数值均为整数。对于每个 $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$

第 $i=3,7,10$ 的事件为第三种事件，因此你应当输出这些事件时集合中最小 ID 的人：$1, 2, 4$。

标签: AtCoder|abc294D

来源

AtCoder|abc294D