当前位置:首页 > 贪心 > 正文
洛谷P9870双序列拓展(NOIP2023)
246+

题目大意:两个序列a和b,他们的拓展是值序列中的每个元素,可以在原位置复制任意多个,是否满足a的拓展每个元素都小于b的拓展呢?都大于也行。

题目描述

称某个序列 $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

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

输出样例 #1

1001

说明

**【样例解释 #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$ 两两不同。

|测试点编号|$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$ 唯一的一个最大值。

解题思路

暴力可以获得35~70分,其实就是暴力匹配。正解从特殊性质那里思考而来。

首先,要看得懂题意,差值相乘大于0,就是同为正数或者负数,也就是某个数列每个数都比另一个数列小(说成大也可以)。

特殊性质提到,序列a的最小值在末尾,序列b的最大值也在末尾,显然就是要序列a的拓展每个元素都要小于b的拓展。

如何把规模缩小?让最小值变为次小值,或者让最大值变为次大值。

a a a a a a a 次小 a a a a a 最小

b b b b 次大 b b b b b b b 最大

什么情况下,可以删掉a中次小后面的数字?只要最小能消掉的b,也能够被次小消掉就行。具体一点,就是次小值比b中的最小值要小,就用b的最大值消掉他们。如果b的最大值消不掉某个a,那就无解了,因为a中有比他更大的,a不可能总小于b。

同理,消掉次大后面的数字,只需要次大值能独当一面,比a中的最大值都要大就行,那么a中的元素都能被他消掉,最大值就没有利用价值了。如果a的最小值消不掉某个b,那么也是无解,因为b中有更小的,b不能能总大于a。

为了保证时间复杂度,需要预处理前缀最小值和最大值的位置,这样时间复杂度是$O(q*n)$,加上暴力代码70分就到手。

满分的话,没有规定最小值和最大值在末尾,那就人工找到a的最小值和b的最大值位置,分开两半处理就行——左边按特殊性质,右边倒过来做法一样。

程序实现

不妨设a小于b,如果遇到不满足条件的,那就交换a和b。

暴力$O(qn^2)$做法,运气好70分。

About

坚决不Copy代码!

本文标签:,,,,,,,

报歉!评论已关闭.