#P1366. 有序表的合并

有序表的合并

题目描述

给出两个数列 a,ba, b,均按不降序排序。其中保证 aa 中没有重复的数字。

现在请你求出:aa 中每一个数字在 bb 中出现了几次?

输入格式

本题单测试点内有多组测试数据

输入的第一行是一个整数,表示数据组数 TT。接下来按顺序给出每组数据的输入信息:

第一行为两个整数,依次表示 aa 数列的长度 nnbb 数列的长度 mm
第二行有 nn 个整数表示数列 aa,第 ii 个整数表示 aia_i
第三行有 mm 个整数表示数列 bb,第 ii 个整数表示 bib_i

输出格式

为了避免输出过大,对于每组数据,请你输出一行一个整数,表示数列 aa 的每个数在 bb 中出现次数的按位异或和

形式化的,设 aia_ibb 中出现了 cic_i 次,则你需要输出 c1c2cnc_1 \bigoplus c_2 \bigoplus \dots \bigoplus c_n 的值,其中 \bigoplus 表示按位异或操作。你可以参考提示来完成计算。

1
3 5
1 3 6
1 3 3 5 5
3
1
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5
2
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
2

提示

样例 1 解释

  • a1=1a_1 = 1bb 中出现了 11 次。
  • a2=3a_2 = 3bb 中出现了 22 次。
  • a3=6a_3 = 6bb 中出现了 00 次。

故输出为 12=31 \bigoplus 2 = 3

样例 2 解释

1,4,51, 4, 5 分别在 bb 中出现了 2,1,12, 1, 1 次,故输出为 211=22 \bigoplus 1 \bigoplus 1 = 2

数据规模与约定

对于全部的测试点,保证:

  • 1T101 \leq T \leq 10
  • 1n,m1071 \leq n, m \leq 10^7(n+m)107\sum (n + m) \leq 10^7
  • 1ai,bi<2641 \leq a_i, b_i < 2^{64},且 ai<ai+1a_i < a_{i + 1}bibi+1b_i \leq b_{i + 1}

其中 (n+m)\sum (n+m) 表示单测试点内所有 nnmm 的和,即输入数列的总长度不超过 10710^7

提示

  • 请注意大量数据读入对程序效率造成的影响,选择合适的读入方式,避免超时。
  • 请采用合适的数据类型存储变量,避免溢出。
  • 如果你不知道什么是按位异或和,可以在你的代码里添加如下的函数:
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 类似,例如,要求数组 aaa1ana_1 \sim a_n 的按位异或和,则调用 getXorSum(a + 1, a + 1 + n),求 a0an1a_0 \sim a_{n - 1} 的按位异或和,则调用 getXorSum(a, a + n)。如果 aastd::vector,则将上述调用代码里的 a 均改为 a.begin() 即可。