5199 - NOIP2023 提高:第三题 双序列拓展

称某个序列 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, vx，表示将 x{p_x} 修改为 v_x$。
• 接下来 k_y 行每行包含两个整数 $p_y, vy，表示将 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}。

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【样例解释 #5】

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

【数据范围】

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

• 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 两两不同。

特殊性质：对于每组询问（包括初始询问和额外询问），保证 x_1 < y_1，且 x_n 是序列 X 唯一的一个最小值，y_m 是序列 Y 唯一的一个最大值。

数据下载 http://oj.tzyz360.com/data/5199/expand.zip