HM263 有序差集

来源： 第 263 集 常用集合算法-set_difference

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

差集要分方向：\(v1\) 对 \(v2\) 的差集，是 \(v1\) 里那些**不属于两容器交集**的元素；\(v2\) 对 \(v1\) 的差集则从 \(v2\) 里去掉交集。两边结果一般不同。

例如 \(v1=0,1,\ldots,9\)，\(v2=5,6,\ldots,14\)，交集是 \(5\ldots9\)，则 \(v1-v2\) 为 \(0\,1\,2\,3\,4\)，\(v2-v1\) 为 \(10\,11\,12\,13\,14\)。

用 set_difference 计算。它要求两个源区间都是**有序序列**（本题保证不下降）。结果写入事先 resize 过的目标 vector。目标容量必须按最坏情况预留：两容器**完全没有交集**时，差集可以大到等于较大的那个源容器，因此容量取 max(v1.size(), v2.size())（可用 max，它也在算法头文件里）。若一个容器完全落在另一个里面，被包含的那边差集长度为 \(0\)。

算法返回差集真实结尾的迭代器。遍历时必须用这个返回值，不能用 target.end()：预留空间里多出来的默认 \(0\) 不是差集的一部分。

对每个方向：先输出差集长度，再按迭代器从 begin 打到返回位置，元素之间一个空格。

输入格式

第一行两个整数 \(n\)、\(m\)。

第二行 \(n\) 个整数，构成有序序列 \(v1\)。

第三行 \(m\) 个整数，构成有序序列 \(v2\)。

当某一侧长度为 \(0\) 时，对应行可以是空行。

输出格式

共五行：

1. CAP、一个空格、目标容器预留容量 \(\max(n,m)\)；
2. \(v1-v2\) 的长度；
3. \(v1-v2\) 的全部元素；
4. \(v2-v1\) 的长度；
5. \(v2-v1\) 的全部元素。

空差集对应的那一行只输出换行。行末换行。

样例

输入 #1

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

输出 #1

CAP 10
5
0 1 2 3 4
5
10 11 12 13 14

输入 #2

3 5
2 3 4
1 2 3 4 5

输出 #2

CAP 5
0

2
1 5

说明

\(0 \le n,m \le 1000\)，元素绝对值不超过 \(10^9\)，两序列各自不下降。

样例 #1 即课堂常用的 \(0\sim9\) 与 \(5\sim14\)。样例 #2 中 \(v1\) 完全落在 \(v2\) 内，\(v1-v2\) 为空；反过来只剩下两端的 \(1\) 与 \(5\)。两序列若没有任何公共元素，差集就是各自的全部元素，这也是容量必须取较大 size 的原因。