A4606 | [NOIP2023] 双序列拓展
来源NOIP提高组 / 2023
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
NOIP2023 T3
称某个序列 $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$。例如，
为了避免你扔硬币蒙混过关，小 R 还给了 $q$ 次额外询问，每次额外询问中小 R 会修改 $X$ 和 $Y$ 中若干元素的值。你需要对每次得到的新的 $X$ 和 $Y$ 都进行上述的判断。
询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。
称某个序列 $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 还给了 $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$ 组额外询问。对于每组额外询问：
输入的第二行包含 $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$ 的条件。
【数据范围】
对于所有测试数据，保证：
特殊性质：对于每组询问（包括初始询问和额外询问），保证 $x_1 y_1$，且 $x_n$ 是序列 $X$ 唯一的一个最小值，$y_m$ 是序列 $Y$ 唯一的一个最大值。
由于 $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$ 唯一的一个最大值。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？