题解：P1366 有序表的合并

原题链接

• 洛谷 P1366 有序表的合并

参考资料

• 双指针 - OI Wiki

解题思路

1. 初始令左右边界 $l=1$ 和 $r=1$。

2. 对于每个元素 $a_i$，执行如下操作：

• 将区间左边界 $l$ 从 $r$ 开始向后枚举，直到 $b_l=a_i$（$l\le m$），说明 $b_l$ 是第一个等于 $a_i$ 的元素。
• 将区间右边界 $r$ 从 $l$ 开始向后枚举，直到 $b_r\not =a_i$（$r\le m$），说明 $b_r$ 是第一个不等于 $a_i$ 的元素。
• 此时 $l-r$ 即为 $a_i$ 出现的个数

3. 最后求出所有数的异或和。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const int N=10000005;
ull a[N],b[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(int i=1;i<=m;i++)
		{
			cin>>b[i];
		}
		int l=1,r=1,ans=0;
		for(int i=1;i<=n;i++)
		{
			l=r;
			while(b[l]<a[i]&&l<=m)l++;
			r=l;
			while(b[r]==a[i]&&r<=m)r++;
			ans^=r-l;
		}
		cout<<ans<<'\n';
	}
	return 0;
}