← 返回题目列表

AtCoder · abc294_d

G. 银行

中文机器翻译题面 查看原题

分数: 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.