P1366 Merging Sorted Sequences

Given two sequences $a, b$, both sorted in non-decreasing order. It is guaranteed that there are no duplicate numbers in $a$. Now, for each number in $a$, determine how many times it appears in $b$.

There are multiple test cases in a single test file. The first line contains an integer $T$, the number of test cases. Then, for each test case, the input is given as follows: - The first line contains two integers, the lengths of sequences $a$ and $b$, denoted by $n$ and $m$. - The second line contains $n$ integers representing sequence $a$, where the $i$-th integer is $a_i$. - The third line contains $m$ integers representing sequence $b$, where the $i$-th integer is $b_i$.

To avoid excessive output, for each test case, output a single integer on one line: the bitwise XOR sum of the occurrence counts of every number of $a$ in $b$. Formally, let $a_i$ appear $c_i$ times in $b$. You need to output $c_1 \bigoplus c_2 \bigoplus \dots \bigoplus c_n$, where $\bigoplus$ denotes the bitwise XOR operation. You may refer to the Hint to complete the computation.

### Explanation of Sample 1 - $a_1 = 1$ appears $1$ time in $b$. - $a_2 = 3$ appears $2$ times in $b$. - $a_3 = 6$ appears $0$ times in $b$. Therefore, the output is $1 \bigoplus 2 = 3$. ### Explanation of Sample 2 $1, 4, 5$ appear $2, 1, 1$ times in $b$, respectively, so the output is $2 \bigoplus 1 \bigoplus 1 = 2$. ### Constraints For all test files, it is guaranteed that: - $1 \leq T \leq 10$; - $1 \leq n, m \leq 10^7$, and $\sum (n + m) \leq 10^7$; - $1 \leq a_i, b_i < 2^{64}$, and $a_i < a_{i + 1}$, $b_i \leq b_{i + 1}$. Here, $\sum (n + m)$ denotes the sum of all $n$ and $m$ within a single test file, i.e., the total length of the input sequences does not exceed $10^7$. ### Notes - Pay attention to the impact of large input on program efficiency. Choose an appropriate input method to avoid timeouts. - Use suitable data types to store variables to avoid overflow. - If you do not know what a bitwise XOR sum is, you can add the following function to your code: ```cpp template T getXorSum(T *begin, T *end) { T ret = 0; for (T *it = begin; it != end; ++it) ret ^= *it; return ret; } ``` This function computes the bitwise XOR sum over a half-open interval of the given array (including `std::vector`). The return type matches the type of the input array. The usage is similar to `std::sort`. For example, to compute the bitwise XOR sum of $a_1 \sim a_n$, call `getXorSum(a + 1, a + 1 + n)`. To compute the bitwise XOR sum of $a_0 \sim a_{n - 1}$, call `getXorSum(a, a + n)`. If $a$ is a `std::vector`, replace `a` in the calls above with `a.begin()` accordingly. Translated by ChatGPT 5