P9870 [NOIP2023] Double Sequence Extension

A sequence $B = \{b_1,b_2,\cdots,b_n\}$ is called an **extension** of another sequence $A = \{a_1,a_2,\cdots,a_m\}$ if and only if there exists a sequence of **positive integers** $L = \{l_1,l_2,\cdots,l_m\}$ such that, after replacing $a_i$ with $l_i$ copies of $a_i$, we obtain the sequence $B$. For example: - $\{1,3,3,3,2,2,2\}$ is an extension of $\{1,3,3,2\}$, with $L = \{1,1,2,3\}$ or $\{1,2,1,3\}$. - However, $\{1,3,3,2\}$ is not an extension of $\{1,3,3,3,2\}$, and $\{1,2,3\}$ is not an extension of $\{1,3,2\}$. Little R gives you two sequences $X$ and $Y$. He wants you to find an extension $F = \{f_i\}$ of $X$ with length $l_0 = 10^{100}$ and an extension $G = \{g_i\}$ of $Y$ with length $l_0$, such that for any $1 \le i , j \le l_0$, we have $(f_i - g_i)(f_j - g_j) > 0$. Since the sequences are too long, you only need to tell Little R whether such two sequences exist. To prevent you from just guessing, Little R also gives $q$ additional queries. In each additional query, Little R will modify the values of some elements in $X$ and $Y$. For each new $X$ and $Y$, you need to make the above decision again. **The queries are independent. In each query, all modifications are applied to the original sequences.**

The first line contains four integers $c, n, m, q$, representing the test point index, the length of sequence $X$, the length of sequence $Y$, and the number of additional queries. For the samples, $c$ indicates that the sample has the same constraints as test point $c$. The second line contains $n$ integers $x_1,x_2,\cdots, x_n$, describing sequence $X$. The third line contains $m$ integers $y_1,y_2,\cdots, y_m$, describing sequence $Y$. Next, $q$ groups of additional queries are given. For each group: - The first line contains two integers $k_x$ and $k_y$, representing the numbers of modifications to sequences $X$ and $Y$, respectively. - The next $k_x$ lines each contain two integers $p_x, v_x$, meaning setting $x_{p_x}$ to $v_x$. - The next $k_y$ lines each contain two integers $p_y, v_y$, meaning setting $y_{p_y}$ to $v_y$.

Output one line containing a `01` sequence of length $(q+1)$. The first element is the answer for the initial query, and the following $q$ elements are the answers for the additional queries in order. For each query, if there exist sequences $F$ and $G$ that satisfy the conditions, output `1`; otherwise output `0`.

**[Sample Explanation #1]** Since $F$ and $G$ are too long, we use ellipses to indicate repeating the last element until the sequence length reaches $l_0$. For example, $\{1,2,3,3,\cdots\}$ means that all elements after the third one are $3$. The following describes four queries in order. The first is the initial query, and the next three are additional queries: 1. $A = \{8,6,9\}$, $B = \{1,7,4\}$. Take $F = \{8,8,6,9,\cdots\}, G = \{1,7,4,4,\cdots\}$. 2. $A = \{8,6,0\}$, $B = \{1,7,4\}$. It can be proven that no solution satisfies the requirement. 3. $A = \{8,6,9\}$, $B = \{8,7,5\}$. It can be proven that no solution satisfies the requirement. 4. $A = \{8,8,9\}$, $B = \{7,7,4\}$. Take $F = \{8,8,9,\cdots\}, G = \{7,7,4,\cdots\}$. **[Sample Explanation #2]** This sample satisfies the constraints of test point $4$. **[Sample Explanation #3]** This sample satisfies the constraints of test point $7$. **[Sample Explanation #4]** This sample satisfies the constraints of test point $9$. **[Sample Explanation #5]** This sample satisfies the constraints of test point $18$. **[Constraints]** For all testdata, it is guaranteed that: - $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$, and the sum of $(k_x+k_y)$ over all additional queries does not exceed $5 \times 10 ^ 5$. - $1 \le p_x \le n$, $1 \le p_y \le m$, $0 \le v_x, v_y < 10 ^ 9$. - For each additional query, all $p_x$ are pairwise distinct, and all $p_y$ are pairwise distinct. |Test Point Index|$n, m \le$|Special Property| |:-:|:-:|:-:| |$1$|$1$|No| |$2$|$2$|No| |$3, 4$|$6$|No| |$5$|$200$|No| |$6, 7$|$2000$|No| |$8, 9$|$4 \times 10 ^ 4$|Yes| |$10, 11$|$1.5 \times 10 ^ 5$|Yes| |$12 \sim 14$|$5 \times 10 ^ 5$|Yes| |$15, 16$|$4 \times 10 ^ 4$|No| |$17, 18$|$1.5 \times 10 ^ 5$|No| |$19, 20$|$5 \times 10 ^ 5$|No| Special property: For each query (including the initial query and additional queries), it is guaranteed that $x_1 < y_1$, and $x_n$ is the unique minimum value in sequence $X$, while $y_m$ is the unique maximum value in sequence $Y$. Translated by ChatGPT 5