UOJ Logo Universal Online Judge

UOJ

#764. 【NOI2022】众数

附件下载 统计

对于一个序列,定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入,在本题中请以题面中给出的定义为准。

一开始给定 $n$ 个长度不一的正整数序列,编号为 $1 \sim n$,初始序列可以为空。这 $n$ 个序列被视为存在,其他编号对应的序列视为不存在。

有 $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$,且拼接得到的序列非空。注意:不保证 $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$。

输入格式

输入的第一行包含两个正整数 $n$ 和 $q$,分别表示数列的个数和操作的次数,保证 $n \le 5 \times {10}^5$,$q \le 5 \times {10}^5$。

接下来 $n$ 行,第 $i$ 行表示编号为 $i$ 的数列。每一行的第一个非负整数 $l_i$ 表示初始第 $i$ 号序列的数字个数,接下来有 $l_i$ 个正整数 $a_{i, j}$ 按顺序表示数列中的数字。假定 $C_l = \sum l_i$ 代表输入序列长度之和,则保证 $C_l \le 5 \times {10}^5$,$a_{i,j} \le n + q$。

接下来 $q$ 行,每行若干个正整数,表示一个操作,并按照题面描述中的格式输入。假定 $C_m = \sum m$ 代表所有操作 $3$ 需要拼接的序列个数之和,则保证 $C_m \le 5 \times {10}^5$。

输出格式

对于每次询问,一行输出一个整数表示对应的答案。

样例一

input

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

output

1
3
-1
3
-1

explanation

第一次询问查询序列 $1$ 的众数。由于序列包含两个 $1$,超过序列长度的一半,因此众数为 $1$。

第二次询问查询序列 $2$ 的众数。由于序列只包含 $3$,因此众数为 $3$。

第三次询问询问序列 $3$ 的众数。此时序列 $3$ 为 $(3, 3, 3, 1, 1, 2)$,不存在出现次数大于 $3$ 次的数,因此输出为 -1

样例二

input

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

output

-1
2
2
4

explanation

第一次询问查询序列 $1, 2, 3, 4$ 拼接后得到的序列的众数。拼接的结果为 $(1, 2, 3, 4)$,不存在出现次数大于两次的数,因此输出为 $-1$。

第四次询问查询序列 $1, 2, 3, 4$ 拼接后得到的序列的众数。拼接的结果为 $(1, 2, 2, 4, 4, 4, 4)$,众数为 $4$。

样例三

见附件下载。

该样例满足测试点 $1 \sim 3$ 的限制。

样例四

见附件下载。

该样例满足测试点 $11 \sim 12$ 的限制。

数据范围

对于所有测试数据,保证 $1 \le n, q, C_m, C_l \le 5 \times {10}^5$。

$n, q$ $C_m, C_l$ 测试点编号 特殊性质 A 特殊性质 B 特殊性质 C
$\le 300$ $\le 300$ $1 \sim 3$
$\le 4000$ $\le 4000$ $4 \sim 7$
$\le {10}^5$ $\le {10}^5$ $8$
$9$
$10$
$11 \sim 12$
$13$
$\le 5 \times {10}^5$ $\le 5 \times {10}^5$ $14$
$15$
$16$
$17 \sim 18$
$19 \sim 20$
  • 特殊性质 A:保证 $n = 1$ 且没有操作 $4$。
  • 特殊性质 B:保证任意时刻任何序列中只有数字 $1$ 和 $2$。
  • 特殊性质 C:保证没有操作 $2$。

时间限制:$1\texttt{s}$

空间限制:$1\texttt{GB}$