{"problem":{"name":"[NOI2022] 众数","description":{"content":"**对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。** 一开始给定 $n$ 个长度不一的正整数序列，编号为 $1 \\sim n$，初始序列可以为空。这 $n$ 个序列被视为存在，其他编号对应的序列视为不存在。 有 $q$ 次操作，操作有以下类型: - $1 \\ x \\ y$：在 $x$ 号序列末尾插入数字 $y$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8496"},"statements":[{"statement_type":"Markdown","content":"**对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。**\n\n一开始给定 $n$ 个长度不一的正整数序列，编号为 $1 \\sim n$，初始序列可以为空。这 $n$ 个序列被视为存在，其他编号对应的序列视为不存在。\n\n有 $q$ 次操作，操作有以下类型:\n\n- $1 \\ x \\ y$：在 $x$ 号序列末尾插入数字 $y$。保证 $x$ 号序列存在，且 $1 \\le x, y \\le n + q$。\n- $2 \\ x$：删除 $x$ 号序列末尾的数字，保证 $x$ 号序列存在、非空，且 $1 \\le x \\le n + q$。\n- $3 \\ m \\ x_1 \\ x_2 \\dots \\ 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}$ 互不相同，询问中的合并操作不会对后续操作产生影响。**\n- $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\n## Input\n\n输入的第一行包含两个正整数 $n$ 和 $q$，分别表示数列的个数和操作的次数，保证 $n \\le 5 \\times {10}^5$、$q \\le 5 \\times {10}^5$。\n\n接下来 $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$。\n\n接下来 $q$ 行，每行若干个正整数，表示一个操作，并按照题面描述中的格式输入。\n\n假定 $C_m = \\sum m$ 代表所有操作 $3$ 需要拼接的序列个数之和，则保证 $C_m \\le 5 \\times {10}^5$。\n\n## Output\n\n对于每次询问，一行输出一个整数表示对应的答案。\n\n[samples]\n\n## Note\n\n**【样例解释 \\#1】**\n\n第一次询问查询序列 $1$ 的众数。由于序列包含两个 $1$，超过序列长度的一半，因此众数为 $1$。\n\n第二次询问查询序列 $2$ 的众数。由于序列只包含 $3$，因此众数为 $3$。\n\n第三次询问询问序列 $3$ 的众数。此时序列 $3$ 为 $(3, 3, 3, 1, 1, 2)$，不存在出现次数大于 $3$ 次的数，因此输出为 $-1$。\n\n----\n\n**【样例解释 \\#2】**\n\n第一次询问查询序列 $1, 2, 3, 4$ 拼接后得到的序列的众数。拼接的结果为 $(1, 2, 3, 4)$，不存在出现次数大于两次的数，因此输出为 $-1$。\n\n第四次询问查询序列 $1, 2, 3, 4$ 拼接后得到的序列的众数。拼接的结果为 $(1, 2, 2, 4, 4, 4, 4)$，众数为 $4$。\n\n----\n\n**【样例 \\#3】**\n\n见附件中的 `major/major3.in` 与 `major/major3.ans`。\n\n该样例满足测试点 $1 \\sim 3$ 的限制。\n\n----\n\n**【样例 \\#4】**\n\n见附件中的 `major/major4.in` 与 `major/major4.ans`。\n\n该样例满足测试点 $11 \\sim 12$ 的限制。\n\n----\n\n**【数据范围】**\n\n对于所有测试数据，保证 $1 \\le n, q, C_m, C_l \\le 5 \\times {10}^5$。\n\n| $n, q$ | $C_m, C_l$ | 测试点编号 | 特殊性质 A | 特殊性质 B | 特殊性质 C |\n|:-:|:-:|:-:|:-:|:-:|:-:|\n| $\\le 300$ | $\\le 300$ | $1 \\sim 3$ | 否 | 否 | 是 |\n| $\\le 4000$ | $\\le 4000$ | $4 \\sim 7$ | 否 | 否 | 是 |\n| $\\le {10}^5$ | $\\le {10}^5$ | $8$ | 是 | 是 | 是 |\n| $\\le {10}^5$ | $\\le {10}^5$ | $9$ | 是 | 否 | 否 |\n| $\\le {10}^5$ | $\\le {10}^5$ | $10$ | 否 | 是 | 否 |\n| $\\le {10}^5$ | $\\le {10}^5$ | $11 \\sim 12$ | 否 | 否 | 是 |\n| $\\le {10}^5$ | $\\le {10}^5$ | $13$ | 否 | 否 | 否 |\n| $\\le 5 \\times {10}^5$ | $\\le 5 \\times {10}^5$ | $14$ | 是 | 是 | 是 |\n| $\\le 5 \\times {10}^5$ | $\\le 5 \\times {10}^5$ | $15$ | 是 | 否 | 否 |\n| $\\le 5 \\times {10}^5$ | $\\le 5 \\times {10}^5$ | $16$ | 否 | 是 | 否 |\n| $\\le 5 \\times {10}^5$ | $\\le 5 \\times {10}^5$ | $17 \\sim 18$ | 否 | 否 | 是 |\n| $\\le 5 \\times {10}^5$ | $\\le 5 \\times {10}^5$ | $19 \\sim 20$ | 否 | 否 | 否 |\n\n特殊性质 A：保证 $n = 1$ 且没有操作 $4$。  \n特殊性质 B：保证任意时刻任何序列中只有数字 $1$ 和 $2$。  \n特殊性质 C：保证没有操作 $2$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8496","tags":["2022","NOI","O2优化"],"sample_group":[["2 8\n3 1 1 2\n3 3 3 3\n3 1 1\n3 1 2\n4 2 1 3\n3 1 3\n2 3\n3 1 3\n1 3 1\n3 1 3\n","1\n3\n-1\n3\n-1\n"],["4 9\n1 1\n1 2\n1 3\n1 4\n3 4 1 2 3 4\n1 1 2\n3 2 1 2\n2 3\n3 3 1 2 3\n1 4 4\n1 4 4\n1 4 4\n3 4 1 2 3 4\n","-1\n2\n2\n4\n"]],"created_at":"2026-03-03 11:09:25"}}