【NOIP2023】双序列拓展 - 题目

称某个序列 $B = {b_{1}, b_{2}, \dots, b_{n}}$ 是另一个序列 $A = {a_{1}, a_{2}, \dots, a_{m}}$ 的拓展当且仅当存在正整数序列 $L = {l_{1}, l_{2}, \dots, l_{m}}$ ，将 $a_{i}$ 替换为 $l_{i}$ 个 $a_{i}$ 后得到序列 $B$ 。例如，

${1, 3, 3, 3, 2, 2, 2}$ 是 ${1, 3, 3, 2}$ 的拓展，取 $L = {1, 1, 2, 3}$ 或 ${1, 2, 1, 3}$ ；
而 ${1, 3, 3, 2}$ 不是 ${1, 3, 3, 3, 2}$ 的拓展， ${1, 2, 3}$ 不是 ${1, 3, 2}$ 的拓展。

小 R 给了你两个序列 $X$ 和 $Y$ ，他希望你找到 $X$ 的一个长度为 $l_{0} = 10^{100}$ 的拓展 $F = {f_{i}}$ 以及 $Y$ 的一个长度为 $l_{0}$ 的拓展 $G = {g_{i}}$ ，使得任意 $1 \leq i, j \leq l_{0}$ 都有 $(f_{i} - g_{i}) (f_{j} - g_{j}) > 0$ 。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。

为了避免你扔硬币蒙混过关，小 R 还给了 $q$ 次额外询问，每次额外询问中小 R 会修改 $X$ 和 $Y$ 中若干元素的值。你需要对每次得到的新的 $X$ 和 $Y$ 都进行上述的判断。

询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。

输入格式

输入的第一行包含四个整数 $c, n, m, q$ ，分别表示测试点编号、序列 $X$ 的长度、序列 $Y$ 的长度和额外询问的个数。对于样例， $c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

输入的第二行包含 $n$ 个整数 $x_{1}, x_{2}, \dots, x_{n}$ ，描述序列 $X$ 。

输入的第三行包含 $m$ 个整数 $y_{1}, y_{2}, \dots, y_{m}$ ，描述序列 $Y$ 。

接下来依次描述 $q$ 组额外询问。对于每组额外询问：

输入的第一行包含两个整数 $k_{x}$ 和 $k_{y}$ ，分别表示对序列 $X$ 和 $Y$ 产生的修改个数。
接下来 $k_{x}$ 行每行包含两个整数 $p_{x}, v_{x}$ ，表示将 $x_{p_{x}}$ 修改为 $v_{x}$ 。
接下来 $k_{y}$ 行每行包含两个整数 $p_{y}, v_{y}$ ，表示将 $y_{p_{y}}$ 修改为 $v_{y}$ 。

输出格式

输出一行，其中包含一个长度为 $(q + 1)$ 的 01 序列，序列的第一个元素表示初始询问的答案，之后 $q$ 个元素依次表示每组额外询问的答案。对于每个询问，如果存在满足题目条件的序列 $F$ 和 $G$ ，输出 1，否则输出 0。

样例一

input

output

提示

【样例解释 #1】

由于 $F$ 和 $G$ 太长，用省略号表示重复最后一个元素直到序列长度为 $l_{0}$ 。如 ${1, 2, 3, 3, \dots}$ 表示序列从第三个元素之后都是 $3$ 。

以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问：

$A = {8, 6, 9}$ ， $B = {1, 7, 4}$ ，取 $F = {8, 8, 6, 9, \dots}, G = {1, 7, 4, 4, \dots}$ ；
$A = {8, 6, 0}$ ， $B = {1, 7, 4}$ ，可以证明不存在满足要求的方案；
$A = {8, 6, 9}$ ， $B = {8, 7, 5}$ ，可以证明不存在满足要求的方案；
$A = {8, 8, 9}$ ， $B = {7, 7, 4}$ ，取 $F = {8, 8, 9, \dots}, G = {7, 7, 4, \dots}$ 。

【样例解释 #2】

该组样例满足测试点 $4$ 的条件。

【样例解释 #3】

该组样例满足测试点 $7$ 的条件。

【样例解释 #4】

该组样例满足测试点 $9$ 的条件。

【样例解释 #5】

该组样例满足测试点 $18$ 的条件。

【数据范围】

对于所有测试数据，保证：

$1 \leq n, m \leq 5 \times 10^{5}$ ；
$0 \leq q \leq 60$ ；
$0 \leq x_{i}, y_{i} < 10^{9}$ ；
$0 \leq k_{x}, k_{y} \leq 5 \times 10^{5}$ ，且所有额外询问的 $(k_{x} + k_{y})$ 的和不超过 $5 \times 10^{5}$ ；
$1 \leq p_{x} \leq n$ ， $1 \leq p_{y} \leq m$ ， $0 \leq v_{x}, v_{y} < 10^{9}$ ；
对于每组额外询问， $p_{x}$ 两两不同， $p_{y}$ 两两不同。

测试点编号	$n, m \leq$	特殊性质
$1$	$1$	否
$2$	$2$	否
$3, 4$	$6$	否
$5$	$200$	否
$6, 7$	$2000$	否
$8, 9$	$4 \times 10^{4}$	是
$10, 11$	$1.5 \times 10^{5}$	是
$12 \sim 14$	$5 \times 10^{5}$	是
$15, 16$	$4 \times 10^{4}$	否
$17, 18$	$1.5 \times 10^{5}$	否
$19, 20$	$5 \times 10^{5}$	否

特殊性质：对于每组询问（包括初始询问和额外询问），保证 $x_{1} < y_{1}$ ，且 $x_{n}$ 是序列 $X$ 唯一的一个最小值， $y_{m}$ 是序列 $Y$ 唯一的一个最大值。

时间限制： $1s$

空间限制： $512MB$

Universal Online Judge

UOJ

#836. 【NOIP2023】双序列拓展

输入格式

输出格式

样例一

input

output

提示