#NOIP2023C. 双序列拓展

双序列拓展

题目描述

称某个序列 B={b1,b2,,bn}B = \{b_1,b_2,\cdots,b_n\} 是另一个序列 A={a1,a2,,am}A = \{a_1,a_2,\cdots,a_m\}拓展当且仅当存在正整数序列 L={l1,l2,,lm}L = \{l_1,l_2,\cdots,l_m\},将 aia_i 替换为 lil_iaia_i 后得到序列 BB。例如,

  • {1,3,3,3,2,2,2}\{1,3,3,3,2,2,2\}{1,3,3,2}\{1,3,3,2\} 的拓展,取 L={1,1,2,3}L = \{1,1,2,3\}{1,2,1,3}\{1,2,1,3\}
  • {1,3,3,2}\{1,3,3,2\} 不是 {1,3,3,3,2}\{1,3,3,3,2\} 的拓展,{1,2,3}\{1,2,3\} 不是 {1,3,2}\{1,3,2\} 的拓展。

小 R 给了你两个序列 XXYY,他希望你找到 XX 的一个长度为 l0=10100l_0 = 10^{100} 的拓展 F={fi}F = \{f_i\} 以及 YY 的一个长度为 l0l_0 的拓展 G={gi}G = \{g_i\},使得任意 1i,jl01 \le i , j \le l_0 都有 (figi)(fjgj)>0(f_i - g_i)(f_j - g_j) > 0。由于序列太长,你只需要告诉小 R 是否存在这样的两个序列即可。

为了避免你扔硬币蒙混过关,小 R 还给了 qq 次额外询问,每次额外询问中小 R 会修改 XXYY 中若干元素的值。你需要对每次得到的新的 XXYY 都进行上述的判断。

询问之间是独立的,每次询问中涉及的修改均在原始序列上完成。

输入格式

输入的第一行包含四个整数 c,n,m,qc, n, m, q,分别表示测试点编号、序列 XX 的长度、序列 YY 的长度和额外询问的个数。对于样例,cc 表示该样例与测试点 cc 拥有相同的限制条件。

输入的第二行包含 nn 个整数 x1,x2,,xnx_1,x_2,\cdots, x_n,描述序列 XX

输入的第三行包含 mm 个整数 y1,y2,,ymy_1,y_2,\cdots, y_m,描述序列 YY

接下来依次描述 qq 组额外询问。对于每组额外询问:

  • 输入的第一行包含两个整数 kxk_xkyk_y,分别表示对序列 XXYY 产生的修改个数。
  • 接下来 kxk_x 行每行包含两个整数 px,vxp_x, v_x,表示将 xpxx_{p_x} 修改为 vxv_x
  • 接下来 kyk_y 行每行包含两个整数 py,vyp_y, v_y,表示将 ypyy_{p_y} 修改为 vyv_y

输出格式

输出一行,其中包含一个长度为 (q+1)(q+1)01 序列,序列的第一个元素表示初始询问的答案,之后 qq 个元素依次表示每组额外询问的答案。对于每个询问,如果存在满足题目条件的序列 FFGG,输出 1,否则输出 0

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

提示

【样例解释 #1】

由于 FFGG 太长,用省略号表示重复最后一个元素直到序列长度为 l0l_0。如 {1,2,3,3,}\{1,2,3,3,\cdots\} 表示序列从第三个元素之后都是 33

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

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

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【样例解释 #5】

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

【数据范围】

对于所有测试数据,保证:

  • 1n,m5×1051 \le n, m \le 5 \times 10 ^ 5
  • 0q600 \le q \le 60
  • 0xi,yi<1090 \le x_i, y_i < 10 ^ 9
  • 0kx,ky5×1050 \le k_x, k_y \le 5 \times 10 ^ 5,且所有额外询问的 (kx+ky)(k_x+k_y) 的和不超过 5×1055 \times 10 ^ 5
  • 1pxn1 \le p_x \le n1pym1 \le p_y \le m0vx,vy<1090 \le v_x, v_y < 10 ^ 9
  • 对于每组额外询问,pxp_x 两两不同,pyp_y 两两不同。
测试点编号 n,mn, m \le 特殊性质
11
22
3,43, 4 66
55 200200
6,76, 7 20002000
8,98, 9 4×1044 \times 10 ^ 4
10,1110, 11 1.5×1051.5 \times 10 ^ 5
121412 \sim 14 5×1055 \times 10 ^ 5
15,1615, 16 4×1044 \times 10 ^ 4
17,1817, 18 1.5×1051.5 \times 10 ^ 5
19,2019, 20 5×1055 \times 10 ^ 5

特殊性质:对于每组询问(包括初始询问和额外询问),保证 x1<y1x_1 < y_1,且 xnx_n 是序列 XX 唯一的一个最小值,ymy_m 是序列 YY 唯一的一个最大值。