题目

双序列拓展

提交数: 15, 通过率: 0%, 平均分: 48.33

题目描述:

称某个序列 \(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\}\) 的拓展，取 \(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 \le i , j \le 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,\cdots, x_n\)，描述序列 \(X\)。

输入的第三行包含 \(m\) 个整数 \(y_1,y_2,\cdots, 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,\cdots\}\) 表示序列从第三个元素之后都是 \(3\)。

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

1. \(A = \{8,6,9\}\)，\(B = \{1,7,4\}\)，取 \(F = \{8,8,6,9,\cdots\}, G = \{1,7,4,4,\cdots\}\)；
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,\cdots\}, G = \{7,7,4,\cdots\}\)。

【数据范围】

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

- \(1 \le n, m \le 5 \times 10 ^ 5\)；
- \(0 \le q \le 60\)；
- \(0 \le x_i, y_i < 10 ^ 9\)；
- \(0 \le k_x, k_y \le 5 \times 10 ^ 5\)，且所有额外询问的 \((k_x+k_y)\) 的和不超过 \(5 \times 10 ^ 5\)；
- \(1 \le p_x \le n\)，\(1 \le p_y \le m\)，\(0 \le v_x, v_y < 10 ^ 9\)；
- 对于每组额外询问，\(p_x\) 两两不同，\(p_y\) 两两不同。

|测试点编号|\(n, m \le\)|特殊性质|
|:-:|:-:|:-:|
|\(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