← 返回题目列表

AtCoder · abc298_c

F. 卡片查询问题

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

分数: 300 点

问题陈述

我们有 N 盒子编号 1 to N 最初是空的,并且空白卡的数量不受限制。
流程 Q 按顺序查询。查询有以下三种。

  • 1 i j \colon 写入号码 i 在一张空白卡上并将其放入盒子中 j.
  • 2 i \colon 报告框中卡片上写的所有数字 i, 按升序排列.
  • 3 i \colon 报告包含该号码的卡片的箱子的所有箱子号码 i, 按升序排列.

此处,请注意以下事项。

  • 在第二类查询中,if 框 i 包含多张具有相同号码的卡片,该号码的打印次数应等于这些卡片的数量。
  • 在第三类查询中,即使一个盒子包含多张卡片,其编号为 i,该箱子的箱号只能打印一次。

约束

  • 1 \leq N, Q \leq 2 \times 10^5
  • 对于第一类查询:
    • 1 \leq i \leq 2 \times 10^5
    • 1 \leq j \leq N
  • 对于第二类查询:
    • 1 \leq i \leq N
    • 盒子 给出此查询时, i 包含一些卡片。
  • 对于第三类查询:
    • 1 \leq i \leq 2 \times 10^5
    • 有些盒子里有一张卡片,上面有号码 i 给出此查询时。
  • 最多 将报告 2 \times 10^5 号码。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

在这里, \mathrm{query}_q 表示 q-th 查询,采用以下格式之一:

1 i j
2 i
3 i

输出

按顺序回答第二类和第三类询问。
对于每个查询,打印一行包含要报告的元素 按升序排列,中间有空格。


示例输入 1

5
8
1 1 1
1 2 4
1 1 4
2 4
1 1 4
2 4
3 1
3 2

示例输出 1

1 2
1 1 2
1 4
4

让我们按顺序处理查询。

  • 写 1 放在卡片上并将其放入盒子中 1.
  • 写 2 放在卡片上并将其放入盒子中 4.
  • 写 1 放在卡片上并将其放入盒子中 4.
  • 盒子 给出此查询时, 4 包含带有数字的卡片 1 和 2.
    • 打印 1 和 2 按此顺序。
  • 写 1 放在卡片上并将其放入盒子中 4.
  • 盒子 给出此查询时, 4 包含带有数字的卡片 1, 1,和 2.
    • 请注意,您应该打印 1 两次。
  • 盒子 1 和 4 包含一张带有编号的卡片 1.
    • 请注意,您应该打印 4 仅一次,即使盒子 4 包含两张卡片,其编号为 1.
  • 盒子 4 包含一张卡片,其编号为 2.

示例输入 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

示例输出 2

1 2 200000
1