102982: [Atcoder]ABC298 C - Cards Query Problem

Problem Statement

We have $N$ boxes numbered $1$ to $N$ that are initially empty, and an unlimited number of blank cards.
Process $Q$ queries in order. There are three kinds of queries as follows.

• 1 i j $\colon$ Write the number $i$ on a blank card and put it into box $j$.
• 2 i $\colon$ Report all numbers written on the cards in box $i$, in ascending order.
• 3 i $\colon$ Report all box numbers of the boxes that contain a card with the number $i$, in ascending order.

Here, note the following.

• In a query of the second kind, if box $i$ contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number $i$, the box number of that box should be printed only once.

Constraints

• $1 \leq N, Q \leq 2 \times 10^5$
• For a query of the first kind:
  • $1 \leq i \leq 2 \times 10^5$
  • $1 \leq j \leq N$
• For a query of the second kind:
  • $1 \leq i \leq N$
  • Box $i$ contains some cards when this query is given.
• For a query of the third kind:
  • $1 \leq i \leq 2 \times 10^5$
  • Some boxes contain a card with the number $i$ when this query is given.
• At most $2 \times 10^5$ numbers are to be reported.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Here, $\mathrm{query}_q$ denotes the $q$-th query, which is in one of the following formats:

$1$ $i$ $j$

$2$ $i$

$3$ $i$

Output

Respond to the queries of the second and third kinds in order.
For each of those queries, print one line containing the elements to be reported in ascending order, with spaces in between.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write $1$ on a card and put it into box $1$.
• Write $2$ on a card and put it into box $4$.
• Write $1$ on a card and put it into box $4$.
• Box $4$ contains cards with the numbers $1$ and $2$.
  • Print $1$ and $2$ in this order.
• Write $1$ on a card and put it into box $4$.
• Box $4$ contains cards with the numbers $1$, $1$, and $2$.
  • Note that you should print $1$ twice.
• Boxes $1$ and $4$ contain a card with the number $1$.
  • Note that you should print $4$ only once, even though box $4$ contains two cards with the number $1$.
• Boxes $4$ contains a card with the number $2$.

Sample Input 2

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

Sample Output 2

1 2 200000
1

问题描述

我们有编号为1到N的初始为空的N个盒子和无限数量的空白卡片。

• 1 i j $\colon$ 在一张空白卡片上写上数字i并将其放入编号为j的盒子中。
• 2 i $\colon$ 按升序报告编号为i的盒子中的卡片上的所有数字。
• 3 i $\colon$ 按升序报告包含数字i的卡片的盒子的编号。

注意以下几点。

• 在第二种查询中，如果编号为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个查询，可以是以下格式之一：

$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的盒子包含两个带有数字1的卡片，你也应该只打印一次4。
• 编号为4的盒子包含带有数字2的卡片。

样例输入2

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

样例输出2

1 2 200000
1