题目

双序列拓展

提交数: 20, 通过率: 0%, 平均分: 39.25

题目描述:

称某个序列 $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`。

样例输入:

样例输出:

提示:

【样例解释 #1】

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

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

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

【数据范围】

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

- $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$ 唯一的一个最大值。

时间限制: 1000ms
空间限制: 512MB

来源: NOIP2023提高T3