自动搬运

查看原文

来自洛谷，原作者为

	Usada_Pekora 兎田ぺこら/大傻Peko_Official/AFO

搬运于2025-08-24 21:24:16，当前版本为作者最后更新于2022-12-18 18:29:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意很清晰，在此不再分析，解法要求时间空间都是线性的。

注意到题目给出了一个特殊性质：$a,b$ 都是升序的。

也就是说与 $a_i$ 相等的那些 $b_{l_1\sim r_1}$ 和与 $a_{i+1}$ 相等的那些 $b_{l_2\sim r_2}$ 是彼此不相交的一些数，即若他们都存在，则一定有 $l_2\gt r_1$。

于是从左到右扫一下就好了，对于每个 $a_i$ 我们需要统计值域在 $(a_{i-1},a_i]$ 的 $b_j$，维护一个 $j$ 即可。具体地，我们每次从第一个大于 $a_{i-1}$ 的 $b_j$ 开始往右找到第一个大于 $a_i$ 的 $b_{j^{'}}$，容易发现若我们每次从前一个数继承 $j$，则 $i$ 的移动次数是 $O(n)$ 的，$j$ 的移动次数是 $O(m)$ 的。

复杂度 $O(\sum(n+m))$。

#include <bits/stdc++.h>
using namespace std;
inline uint64_t read() {
	uint64_t x = 0;
	char ch = getchar();
	while (!isdigit(ch))
		ch = getchar();
	while (isdigit(ch))
		x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
	return x;
}
uint64_t a[10000001], b[10000001];
signed main() {
	for (int T = read(), n, m; (T--) && (n = read(), m = read()); ) {
		for (int i = 1; i <= n; i++)
			a[i] = read();
		for (int i = 1; i <= m; i++)
			b[i] = read();
		int j = 1, cnt = 0, ans = 0;
		for (int i = 1; i <= n; i++) {
			cnt = 0;
			while (j <= m && a[i] >= b[j]) {
				cnt += (a[i] == b[j]);
				j++;
			}
			ans ^= cnt;
		}
		printf("%d\n", ans);
	}
	return 0;
}