有序表的合并
题目描述
给出两个数列 $a, b$,均按不降序排序。其中保证 $a$ 中没有重复的数字。
现在请你求出:$a$ 中每一个数字在 $b$ 中出现了几次?
输入输出格式
输入格式
**本题单测试点内有多组测试数据**。
输入的第一行是一个整数,表示数据组数 $T$。接下来按顺序给出每组数据的输入信息:
第一行为两个整数,依次表示 $a$ 数列的长度 $n$ 和 $b$ 数列的长度 $m$。
第二行有 $n$ 个整数表示数列 $a$,第 $i$ 个整数表示 $a_i$。
第三行有 $m$ 个整数表示数列 $b$,第 $i$ 个整数表示 $b_i$。
输出格式
为了避免输出过大,对于每组数据,请你输出一行一个整数,表示数列 $a$ 的每个数在 $b$ 中出现次数的**按位异或和**。
形式化的,设 $a_i$ 在 $b$ 中出现了 $c_i$ 次,则你需要输出 $c_1 \bigoplus c_2 \bigoplus \dots \bigoplus c_n$ 的值,其中 $\bigoplus$ 表示按位异或操作。你可以参考提示来完成计算。
输入输出样例
输入样例 #1
1
3 5
1 3 6
1 3 3 5 5
输出样例 #1
3
输入样例 #2
1
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5
输出样例 #2
2
输入样例 #3
2
3 5
1 3 6
1 3 3 5 5
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5
输出样例 #3
3
2
说明
### 样例 1 解释
- $a_1 = 1$ 在 $b$ 中出现了 $1$ 次。
- $a_2 = 3$ 在 $b$ 中出现了 $2$ 次。
- $a_3 = 6$ 在 $b$ 中出现了 $0$ 次。
故输出为 $1 \bigoplus 2 = 3$。
### 样例 2 解释
$1, 4, 5$ 分别在 $b$ 中出现了 $2, 1, 1$ 次,故输出为 $2 \bigoplus 1 \bigoplus 1 = 2$。
### 数据规模与约定
对于全部的测试点,保证:
- $1 \leq T \leq 10$;
- $1 \leq n, m \leq 10^7$,$\sum (n + m) \leq 10^7$;
- $1 \leq a_i, b_i < 2^{64}$,且 $a_i < a_{i + 1}$,$b_i \leq b_{i + 1}$。
其中 $\sum (n+m)$ 表示单测试点内所有 $n$ 与 $m$ 的和,即输入数列的总长度不超过 $10^7$。
### 提示
- 请注意大量数据读入对程序效率造成的影响,选择合适的读入方式,避免超时。
- 请采用合适的数据类型存储变量,避免溢出。
- 如果你不知道什么是按位异或和,可以在你的代码里添加如下的函数:
```cpp
template <class T>
T getXorSum(T *begin, T *end) {
T ret = 0;
for (T *it = begin; it != end; ++it) ret ^= *it;
return ret;
}
```
这一函数的作用是计算传入数组(包括 `std::vector`)某一左闭右开区间的按位异或和,返回值类型与传入数组的类型相同,调用方法与 `std::sort` 类似,例如,要求数组 $a$ 的 $a_1 \sim a_n$ 的按位异或和,则调用 `getXorSum(a + 1, a + 1 + n)`,求 $a_0 \sim a_{n - 1}$ 的按位异或和,则调用 `getXorSum(a, a + n)`。如果 $a$ 是 `std::vector`,则将上述调用代码里的 `a` 均改为 `a.begin()` 即可。