题解：P1366 有序表的合并

· · 题解

解题思路

初始时，令左右边界 l=r=1。

对于每个元素 a_i，执行以下操作：

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

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

参考代码

#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(l<=m&&b[l]<a[i])l++;
            r=l;
            while(r<=m&&b[r]==a[i])r++;
            ans^=r-l;
        }
        cout<<ans<<'\n';
    }
    return 0;
}