分数: 400 点
问题陈述
N 人,有身份证号码 1, 2, \dots, N,正在一家银行前排队。
将会有 Q 事件。可能发生以下三种事件。
1:柜员呼叫未被呼叫的身份证号码最小的人。2 x: 身份证号码的人 x 第一次来到柜员处。 (这里,人 x 已被柜员至少拨打过一次。)3:柜员再次呼叫已被叫过但未来的身份证号最小的人。
打印第三类事件中柜员所呼叫人员的身份证号码。
约束
- 1 \leq N \leq 5 \times 10^5
- 2 \leq Q \leq 5 \times 10^5
- 当所有人都已被呼叫至少一次时,不会发生第一类事件。
- 对于第二类事件,具有 ID 号的人 x 已被柜员至少拨打过一次。
- 对于第二类事件,具有 ID 号的人 x 不会多次到柜员处。
- 当所有已被叫到的人都来到柜员处时,不会发生第三类事件。
- 至少存在一个第三类事件。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出,其中 \text{event}_i 表示 i第事件:
N Q
\text{event}_1
\text{event}_2
\vdots
\text{event}_Q
每个事件的描述采用以下格式之一:
1
2 x
3
输出
打印 X 行,其中 X 是第三类事件的数量。
的
树的 i- 第行应包含被呼叫者的 ID 号 i-第三类事件。
示例输入 1
4 10 1 1 3 2 1 1 2 3 3 1 2 2 3
示例输出 1
1 2 4
对于每个 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.