HM262 有序求并

来源： 第 262 集 常用集合算法-set_union

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

set_union 求两个集合的并集：两段里出现过的值都要，重叠的值只保留一次。例如一段是 \(0\sim 9\)，另一段是 \(5\sim 14\)，并集是 \(0\sim 14\)。两个原容器必须已经有序，结果写入目标容器。

五个参数：第一段起止迭代器、第二段起止迭代器、目标容器起始迭代器。必须包含算法头文件。必须同时满足：

1. 两个原容器都已有序。输入可能无序，先各自排成升序。
2. 目标容器要提前 resize。最坏情况是两段完全不相交，并集长度等于两段长度之和，因此容量取两段 size 相加。有重叠时，多出来的位置保持默认 \(0\)。
3. 算法返回「并集真正结束」的迭代器。遍历并集必须用这个返回值，不能用目标容器的 end()，否则会把后面补的 \(0\) 也扫出来。

先输出用返回迭代器截出来的并集；再输出从目标起始扫到 end() 的整段（含补零）。

输入格式

第一行一个整数 \(n\)。

第二行 \(n\) 个整数。当 \(n=0\) 时本行可以是空行。

第三行一个整数 \(m\)。

第四行 \(m\) 个整数。当 \(m=0\) 时本行可以是空行。

输出格式

共两行：

1. 并集（用返回迭代器截断）；
2. 目标容器从起始到 end() 的全部元素。

同一行内用单个空格分隔，行末换行。对应区间为空时该行只输出换行。

样例

输入 #1

10
0 1 2 3 4 5 6 7 8 9
10
5 6 7 8 9 10 11 12 13 14

输出 #1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 0 0

输入 #2

3
1 2 3
2
8 9

输出 #2

1 2 3 8 9
1 2 3 8 9

说明

\(0 \le n,m \le 1000\)，元素绝对值不超过 \(10^9\)。同一容器内元素互不相同。

样例 #1 容量按最坏情况开成 \(20\)，真正并集只有 \(15\) 个，后五个是补零。样例 #2 两段不相交，容量恰好用完，两行相同。