# #NOI20221A. 「NOI2022」众数 (Majority element)

ID: 267 Type: FileIO (major) 1000ms 1024MiB Tried: 14 Accepted: 4 Difficulty: 9 Uploaded By: Tags>NOI2022

# 「NOI2022」众数 (Majority element)

## 题目描述

$q$ 次操作，操作有以下类型:

• $1 \ x \ y$：在 $x$ 号序列末尾插入数字 $y$。保证 $x$ 号序列存在，且 $1 \le x, y \le n + q$
• $2 \ x$：删除 $x$ 号序列末尾的数字，保证 $x$ 号序列存在、非空，且 $1 \le x \le n + q$
• $3 \ m \ x_1 \ x_2 \ x_m$：将 $x_1, x_2, \ldots, x_m$ 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 $-1$。数据保证对于任意 $1 \le i \le m$$x_i$ 是一个仍然存在的序列，$1 \le x_i \le n + q$，且拼接得到的序列非空。注意：不保证 $\boldsymbol{x_1, \ldots, x_m}$ 互不相同，询问中的合并操作不会对后续操作产生影响。
• $4 \ x_1 \ x_2 \ x_3$：新建一个编号为 $x_3$ 的序列，其为 $x_1$ 号序列后顺次添加 $x_2$ 号序列中数字得到的结果，然后删除 $x_1, x_2$ 对应的序列。此时序列 $x_3$ 视为存在，而序列 $x_1, x_2$ 被视为不存在，在后续操作中也不会被再次使用。保证 $1 \le x_1, x_2, x_3 \le n + q$$x_1 \ne x_2$、序列 $x_1, x_2$ 在操作前存在、且在操作前没有序列使用过编号 $x_3$

## 输出格式

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

1
3
-1
3
-1

4 9
1 1
1 2
1 3
1 4
3 4 1 2 3 4
1 1 2
3 2 1 2
2 3
3 3 1 2 3
1 4 4
1 4 4
1 4 4
3 4 1 2 3 4

-1
2
2
4


## 数据范围与提示

$n, q$ $C_m, C_l$ 测试点编号 特殊性质 A 特殊性质 B 特殊性质 C
$\le 300$ $1 \sim 3$
$\le 4000$ $4 \sim 7$
$\le {10}^5$ $8$
$9$
$10$
$11 \sim 12$
$13$
$\le 5 \times {10}^5$ $14$
$15$
$16$
$17 \sim 18$
$19 \sim 20$