Score : $300$ points

问题描述

我们有 $N$ 个编号为 $1$ 到 $N$ 的空盒子，以及无限数量的空白卡片。
按照顺序处理 $Q$ 个查询请求。查询请求分为以下三种类型。

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

请注意以下几点：

• 对于第二类查询，如果盒子 $i$ 中有多张卡片写着相同的数字，则应打印该数字，其重复次数等于拥有这些卡片的数量。
• 对于第三类查询，即使某个盒子包含多张带有数字 $i$ 的卡片，也只需打印该盒子的编号一次。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:21:56