{"problem":{"name":"[NOIP2023] 双序列拓展","description":{"content":"称某个序列 $B = \\{b_1,b_2,\\cdots,b_n\\}$ 是另一个序列 $A = \\{a_1,a_2,\\cdots,a_m\\}$ 的**拓展**当且仅当存在**正整数**序列 $L = \\{l_1,l_2,\\cdots,l_m\\}$，将 $a_i$ 替换为 $l_i$ 个 $a_i$ 后得到序列 $B$。例如， - $\\{1,3,3,3,2,2,2\\}$ 是 $\\{1,3,3,2\\}","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9870"},"statements":[{"statement_type":"Markdown","content":"称某个序列 $B = \\{b_1,b_2,\\cdots,b_n\\}$ 是另一个序列 $A = \\{a_1,a_2,\\cdots,a_m\\}$ 的**拓展**当且仅当存在**正整数**序列 $L = \\{l_1,l_2,\\cdots,l_m\\}$，将 $a_i$ 替换为 $l_i$ 个 $a_i$ 后得到序列 $B$。例如，\n\n- $\\{1,3,3,3,2,2,2\\}$ 是 $\\{1,3,3,2\\}$ 的拓展，取 $L = \\{1,1,2,3\\}$ 或 $\\{1,2,1,3\\}$；\n- 而 $\\{1,3,3,2\\}$ 不是 $\\{1,3,3,3,2\\}$ 的拓展，$\\{1,2,3\\}$ 不是 $\\{1,3,2\\}$ 的拓展。\n\n小 R 给了你两个序列 $X$ 和 $Y$，他希望你找到 $X$ 的一个长度为 $l_0 = 10^{100}$ 的拓展 $F = \\{f_i\\}$ 以及 $Y$ 的一个长度为 $l_0$ 的拓展 $G = \\{g_i\\}$，使得任意 $1 \\le i , j \\le l_0$ 都有 $(f_i - g_i)(f_j - g_j) > 0$。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。\n\n为了避免你扔硬币蒙混过关，小 R 还给了 $q$ 次额外询问，每次额外询问中小 R 会修改 $X$ 和 $Y$ 中若干元素的值。你需要对每次得到的新的 $X$ 和 $Y$ 都进行上述的判断。\n\n**询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。**\n\n## Input\n\n输入的第一行包含四个整数 $c, n, m, q$，分别表示测试点编号、序列 $X$ 的长度、序列 $Y$ 的长度和额外询问的个数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。\n\n输入的第二行包含 $n$ 个整数 $x_1,x_2,\\cdots, x_n$，描述序列 $X$。\n\n输入的第三行包含 $m$ 个整数 $y_1,y_2,\\cdots, y_m$，描述序列 $Y$。\n\n接下来依次描述 $q$ 组额外询问。对于每组额外询问：\n\n- 输入的第一行包含两个整数 $k_x$ 和 $k_y$，分别表示对序列 $X$ 和 $Y$ 产生的修改个数。\n- 接下来 $k_x$ 行每行包含两个整数 $p_x, v_x$，表示将 $x_{p_x}$ 修改为 $v_x$。\n- 接下来 $k_y$ 行每行包含两个整数 $p_y, v_y$，表示将 $y_{p_y}$ 修改为 $v_y$。\n\n## Output\n\n输出一行，其中包含一个长度为 $(q+1)$ 的 `01` 序列，序列的第一个元素表示初始询问的答案，之后 $q$ 个元素依次表示每组额外询问的答案。对于每个询问，如果存在满足题目条件的序列 $F$ 和 $G$，输出 `1`，否则输出 `0`。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n由于 $F$ 和 $G$ 太长，用省略号表示重复最后一个元素直到序列长度为 $l_0$。如 $\\{1,2,3,3,\\cdots\\}$ 表示序列从第三个元素之后都是 $3$。\n\n以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问：\n\n1. $A = \\{8,6,9\\}$，$B = \\{1,7,4\\}$，取 $F = \\{8,8,6,9,\\cdots\\}, G = \\{1,7,4,4,\\cdots\\}$；\n2. $A = \\{8,6,0\\}$，$B = \\{1,7,4\\}$，可以证明不存在满足要求的方案；\n3. $A = \\{8,6,9\\}$，$B = \\{8,7,5\\}$，可以证明不存在满足要求的方案；\n4. $A = \\{8,8,9\\}$，$B = \\{7,7,4\\}$，取 $F = \\{8,8,9,\\cdots\\}, G = \\{7,7,4,\\cdots\\}$。\n\n**【样例解释 #2】**\n\n该组样例满足测试点 $4$ 的条件。\n\n**【样例解释 #3】**\n\n该组样例满足测试点 $7$ 的条件。\n\n**【样例解释 #4】**\n\n该组样例满足测试点 $9$ 的条件。\n\n**【样例解释 #5】**\n\n该组样例满足测试点 $18$ 的条件。\n\n**【数据范围】**\n\n对于所有测试数据，保证：\n\n- $1 \\le n, m \\le 5 \\times 10 ^ 5$；\n- $0 \\le q \\le 60$；\n- $0 \\le x_i, y_i < 10 ^ 9$；\n- $0 \\le k_x, k_y \\le 5 \\times 10 ^ 5$，且所有额外询问的 $(k_x+k_y)$ 的和不超过 $5 \\times 10 ^ 5$；\n- $1 \\le p_x \\le n$，$1 \\le p_y \\le m$，$0 \\le v_x, v_y < 10 ^ 9$；\n- 对于每组额外询问，$p_x$ 两两不同，$p_y$ 两两不同。\n\n|测试点编号|$n, m \\le$|特殊性质|\n|:-:|:-:|:-:|\n|$1$|$1$|否|\n|$2$|$2$|否|\n|$3, 4$|$6$|否|\n|$5$|$200$|否|\n|$6, 7$|$2000$|否|\n|$8, 9$|$4 \\times 10 ^ 4$|是|\n|$10, 11$|$1.5 \\times 10 ^ 5$|是|\n|$12 \\sim 14$|$5 \\times 10 ^ 5$|是|\n|$15, 16$|$4 \\times 10 ^ 4$|否|\n|$17, 18$|$1.5 \\times 10 ^ 5$|否|\n|$19, 20$|$5 \\times 10 ^ 5$|否|\n\n特殊性质：对于每组询问（包括初始询问和额外询问），保证 $x_1 < y_1$，且 $x_n$ 是序列 $X$ 唯一的一个最小值，$y_m$ 是序列 $Y$ 唯一的一个最大值。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9870","tags":["动态规划 DP","贪心","2023","NOIP 提高组","O2优化","Ad-hoc"],"sample_group":[["3 3 3 3\n8 6 9\n1 7 4\n1 0\n3 0\n0 2\n1 8\n3 5\n1 1\n2 8\n1 7\n","1001"]],"created_at":"2026-03-03 11:09:25"}}