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

「NOI2022」众数 (Majority element)

题目描述

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

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

qq 次操作,操作有以下类型:

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

输入格式

从文件 major.in 中读入数据。

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

接下来 nn 行,第 ii 行表示编号为 ii 的数列。每一行的第一个非负整数 lil_i 表示初始第 ii 号序列的数字个数,接下来有 lil_i 个非负整数 ai,ja_{i,j} 按顺序表示数列中的数字。假定 Cl=liC_l = \sum l_i 代表输入序列长度之和,则保证 Cl5×105C_l \le 5 \times {10}^5ai,jn+qa_{i,j} \le n + q

接下来 qq 行,每行若干个正整数,表示一个操作,并按照题面描述中的格式输入。

假定 Cm=mC_m = \sum m 代表所有操作 33 需要拼接的序列个数之和,则保证 Cm5×105C_m \le 5 \times {10}^5

输出格式

输出到文件 major.out 中。

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

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

样例 3

见附件中的 [major3.in](file://major3.in) 与 [major3.ans](file://major3.ans)。

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

样例 4

见附件中的 [major4.in](file://major4.in) 与 [major4.ans](file://major4.ans)。

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

数据范围与提示

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

n,qn, q Cm,ClC_m, C_l 测试点编号 特殊性质 A 特殊性质 B 特殊性质 C
300\le 300 131 \sim 3
4000\le 4000 474 \sim 7
105\le {10}^5 88
99
1010
111211 \sim 12
1313
5×105\le 5 \times {10}^5 1414
1515
1616
171817 \sim 18
192019 \sim 20

特殊性质 A:保证 n=1n = 1 且没有操作 44
特殊性质 B:保证任意时刻任何序列中只有数字 1122
特殊性质 C:保证没有操作 22