3926. T3-[NOIP2023] 双序列拓展(expand)
时间限制：1000 MS 内存限制：512 MB
题目描述
称某个序列 $ B=\{b_1,b_2,···,b_n\} $ 是另一个序列 $ A=\{a_1,a_2,···,a_m\} $ 的**拓展**当且仅当存在**正整数**序列 $ L=\{l_1,l_2,···,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≤i,j≤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,···,x_n $ ，描述序列 $ X $ 。 输入的第三行包含 $ m $ 个整数 $ y_1,y_2,⋅⋅⋅,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≤n,m≤5×10^5 $ ； - $ 0≤q≤60 $ ； - $ 0≤x_i,y_i<10^9 $ ； - $ 0≤k_x,k_y≤5×10^5 $ ，且所有额外询问的 $ (k_x+k_y) $ 的和不超过 $ 5×10^5 $ ； - $ 1≤p_x≤n，1≤p_y≤m，0≤v_x,v_y<10^9 $ ； - 对于每组额外询问， $ p_x $ 两两不同， $ p_y $ 两两不同。  特殊性质：对于每组询问（包括初始询问和额外询问），保证 $ x_1<y_1 $ ，且 $ x_n $ 是序列 $ X $ 唯一的一个最小值， $ y_m $ 是序列 $ Y $ 唯一的一个最大值。 #### 输入样例： ``` 3 3 3 3 8 6 9 1 7 4 1 0 3 0 0 2 1 8 3 5 1 1 2 8 1 7 ``` #### 输出样例： ``` 1001 ``` #### 样例解释 由于 $ F $ 和 $ G $ 太长，用省略号表示重复最后一个元素直到序列长度为 $ l_0 $ 。 如 $ \{1,2,3,3,···\} $ 表示序列从第三个元素之后都是 $ 3 $ 。 以下依次描述四次询问，其中第一次询问为初始询问，之后的三次为额外询问： 1. $ A=\{8,6,9\}，B=\{1,7,4\} $ ，取 $ F=\{8,8,6,9,···\},G=\{1,7,4,4,···\} $ ； 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,···\},G=\{7,7,4,···\} $ 。