P1366 有序表的合并【洛谷算法习题】-171主机测评

P1366 有序表的合并

网页链接

P1366 有序表的合并在这里插入图片描述

题目描述

给出两个数列

a, b

$a, b$ ，均按不降序排序。其中保证

$a$ 中没有重复的数字。

现在请你求出：

$a$ 中每一个数字在

$b$ 中出现了几次？

输入格式

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

输入的第一行是一个整数，表示数据组数

$T$ 。接下来按顺序给出每组数据的输入信息：

第一行为两个整数，依次表示

$a$ 数列的长度

$n$ 和

$b$ 数列的长度

$m$ 。第二行有

$n$ 个整数表示数列

$a$ ，第

$i$ 个整数表示

a_i

$a_{i}$ 。第三行有

$m$ 个整数表示数列

$b$ ，第

$i$ 个整数表示

b_i

$b_{i}$ 。

输出格式

为了避免输出过大，对于每组数据，请你输出一行一个整数，表示数列

$a$ 的每个数在

$b$ 中出现次数的按位异或和。

形式化的，设

a_i

$a_{i}$ 在

$b$ 中出现了

c_i

$c_{i}$ 次，则你需要输出

⨁

⋯

⨁

c_1 \\bigoplus c_2 \\bigoplus \\dots \\bigoplus c_n

$c_{1} ⨁ c_{2} ⨁ \dots ⨁ c_{n}$ 的值，其中

⨁

\\bigoplus

$⨁$ 表示按位异或操作。你可以参考提示来完成计算。

输入输出样例 #1

输入 #1

1
3 5
1 3 6
1 3 3 5 5

输出 #1

输入输出样例 #2

输入 #2

1
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5

输出 #2

输入输出样例 #3

输入 #3

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

3
2

说明/提示

样例 1 解释

$a_1 = 1 a1=1 在 b b b 中出现了 1 1 1 次。$
$a_2 = 3 a2=3 在 b b b 中出现了 2 2 2 次。$
$a_3 = 6 a3=6 在 b b b 中出现了 0 0 0 次。$

故输出为

⨁

1 \\bigoplus 2 = 3

$1 ⨁ 2 = 3$ 。

样例 2 解释

1, 4, 5

$1, 4, 5$ 分别在

$b$ 中出现了

2, 1, 1

$2, 1, 1$ 次，故输出为

⨁

2 \\bigoplus 1 \\bigoplus 1 = 2

$2 ⨁ 1 ⨁ 1 = 2$ 。

数据规模与约定

对于全部的测试点，保证：

$\\leq T \\leq 10 1≤T≤10；$
$\\leq n, m \\leq 10^7 1≤n,m≤107， ∑ ( n + m ) ≤ 10 7 \\sum (n + m) \\leq 10^7 ∑(n+m)≤107；$
$\\leq a_i, b_i < 2^{64} 1≤ai,bi<264，且 a i < a i + 1 a_i < a_{i + 1} ai<ai+1， b i ≤ b i + 1 b_i \\leq b_{i + 1} bi≤bi+1。$

其中

∑

(

)

\\sum (n+m)

$\sum (n + m)$ 表示单测试点内所有

$n$ 与

$m$ 的和，即输入数列的总长度不超过

10^7

$1 0^{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 类似，例如，要求数组

$a$ 的

∼

a_1 \\sim a_n

$a_{1} \sim a_{n}$ 的按位异或和，则调用 getXorSum(a + 1, a + 1 + n)，求

∼

−

a_0 \\sim a_{n – 1}

$a_{0} \sim a_{n - 1}$ 的按位异或和，则调用 getXorSum(a, a + n)。如果

$a$ 是 std::vector，则将上述调用代码里的 a 均改为 a.begin() 即可。

解题思路

本题是有序数组双指针线性扫描的经典应用题，利用两个数组的有序单调性，以线性时间复杂度完成匹配统计，适配千万级数据规模。

核心利用数组非降的性质，用两个指针分别遍历数组a和b，单向移动无回溯，统计每个a中元素在b里的出现次数，同步计算异或和：

初始化双指针 i=1（遍历a）、j=1（遍历b），匹配计数 num=0，异或和答案 ans=0。

若 b[j] == a[i]：匹配计数加1，j指针右移，继续统计连续相等的元素。

若元素不相等：将当前累计计数异或到答案中；根据大小关系移动对应指针（小的一侧指针右移），并将计数清零。

循环结束后，将最后剩余的匹配计数异或入答案，避免遗漏末尾匹配的元素。

由于数组元素数值范围可达

2^{64}

$2^{64}$ ，使用 unsigned long long 类型存储；输入数据量极大，通过关闭流同步加速输入，保证读取效率。算法总时间复杂度为

(

)

O(n+m)

$O (n + m)$ ，与数组总长度成正比，完美适配数据规模。

总结

核心逻辑：基于有序数组的单调性，双指针单向扫描完成元素匹配计数，同步计算出现次数的异或和。关键操作：双指针无回溯遍历、连续相等元素计数、按位异或累加结果、大输入量IO优化。效率保障：严格线性时间复杂度，指针仅向右移动，无重复遍历，千万级数据可高效处理。

代码简要说明

全局数组定义：开辟长度为1e7+10的全局数组a、b，类型为unsigned long long，适配大数值范围且避免栈溢出。

输入加速：关闭cin同步流并解绑tie，大幅提升海量数据的读取速度。

双指针遍历：i、j分别从数组首元素开始，相等则计数累加并移动j指针；不等则将当前计数异或入答案，移动值较小一侧的指针并重置计数。

收尾处理：循环结束后补充异或最后一次的计数，确保无遗漏。

结果输出：每组数据输出最终的异或和结果。

代码内容

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

#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=1e9+7;

#define XD 114514

ll t;
ull a[10000010], b[10000010];

int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> t;
while(t—)
{
ull n, m;
cin >> n >> m;
for(ll i=1; i<=n; i++) cin >> a[i];
for(ll i=1; i<=m; i++) cin >> b[i];
ll i=1, j=1, num=0, ans=0;
while(i<=n && j<=m)
{
if(a[i] == b[j])
{
num++;
j++;
}
else
{
ans ^= num;
if(a[i] < b[j]) i++;
else j++;
num = 0;
}
}
ans ^= num;
cout << ans << endl;
}
return 0;
}

P1366 有序表的合并【洛谷算法习题】