P1366 有序表的合并网页链接P1366 有序表的合并题目描述给出两个数列a , b a, ba,b均按不降序排序。其中保证a aa中没有重复的数字。现在请你求出a aa中每一个数字在b bb中出现了几次输入格式本题单测试点内有多组测试数据。输入的第一行是一个整数表示数据组数T TT。接下来按顺序给出每组数据的输入信息第一行为两个整数依次表示a aa数列的长度n nn和b bb数列的长度m mm。第二行有n nn个整数表示数列a aa第i ii个整数表示a i a_iai​。第三行有m mm个整数表示数列b bb第i ii个整数表示b i b_ibi​。输出格式为了避免输出过大对于每组数据请你输出一行一个整数表示数列a aa的每个数在b bb中出现次数的按位异或和。形式化的设a i a_iai​在b bb中出现了c i c_ici​次则你需要输出c 1 ⨁ c 2 ⨁ ⋯ ⨁ c n c_1 \bigoplus c_2 \bigoplus \dots \bigoplus c_nc1​⨁c2​⨁⋯⨁cn​的值其中⨁ \bigoplus⨁表示按位异或操作。你可以参考提示来完成计算。输入输出样例 #1输入 #11 3 5 1 3 6 1 3 3 5 5输出 #13输入输出样例 #2输入 #21 9 4 1 2 3 4 5 6 7 8 9 1 1 4 5输出 #22输入输出样例 #3输入 #32 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输出 #33 2说明/提示样例 1 解释a 1 1 a_1 1a1​1在b bb中出现了1 11次。a 2 3 a_2 3a2​3在b bb中出现了2 22次。a 3 6 a_3 6a3​6在b bb中出现了0 00次。故输出为1 ⨁ 2 3 1 \bigoplus 2 31⨁23。样例 2 解释1 , 4 , 5 1, 4, 51,4,5分别在b bb中出现了2 , 1 , 1 2, 1, 12,1,1次故输出为2 ⨁ 1 ⨁ 1 2 2 \bigoplus 1 \bigoplus 1 22⨁1⨁12。数据规模与约定对于全部的测试点保证1 ≤ T ≤ 10 1 \leq T \leq 101≤T≤101 ≤ n , m ≤ 10 7 1 \leq n, m \leq 10^71≤n,m≤107∑ ( n m ) ≤ 10 7 \sum (n m) \leq 10^7∑(nm)≤1071 ≤ a i , b i 2 64 1 \leq a_i, b_i 2^{64}1≤ai​,bi​264且a i a i 1 a_i a_{i 1}ai​ai1​b i ≤ b i 1 b_i \leq b_{i 1}bi​≤bi1​。其中∑ ( n m ) \sum (nm)∑(nm)表示单测试点内所有n nn与m mm的和即输入数列的总长度不超过10 7 10^7107。提示请注意大量数据读入对程序效率造成的影响选择合适的读入方式避免超时。请采用合适的数据类型存储变量避免溢出。如果你不知道什么是按位异或和可以在你的代码里添加如下的函数templateclassTTgetXorSum(T*begin,T*end){T ret0;for(T*itbegin;it!end;it)ret^*it;returnret;}这一函数的作用是计算传入数组包括std::vector某一左闭右开区间的按位异或和返回值类型与传入数组的类型相同调用方法与std::sort类似例如要求数组a aa的a 1 ∼ a n a_1 \sim a_na1​∼an​的按位异或和则调用getXorSum(a 1, a 1 n)求a 0 ∼ a n − 1 a_0 \sim a_{n - 1}a0​∼an−1​的按位异或和则调用getXorSum(a, a n)。如果a aa是std::vector则将上述调用代码里的a均改为a.begin()即可。解题思路本题是有序数组双指针线性扫描的经典应用题利用两个数组的有序单调性以线性时间复杂度完成匹配统计适配千万级数据规模。核心利用数组非降的性质用两个指针分别遍历数组a和b单向移动无回溯统计每个a中元素在b里的出现次数同步计算异或和初始化双指针i1遍历a、j1遍历b匹配计数num0异或和答案ans0。若b[j] a[i]匹配计数加1j指针右移继续统计连续相等的元素。若元素不相等将当前累计计数异或到答案中根据大小关系移动对应指针小的一侧指针右移并将计数清零。循环结束后将最后剩余的匹配计数异或入答案避免遗漏末尾匹配的元素。由于数组元素数值范围可达2 64 2^{64}264使用unsigned long long类型存储输入数据量极大通过关闭流同步加速输入保证读取效率。算法总时间复杂度为O ( n m ) O(nm)O(nm)与数组总长度成正比完美适配数据规模。总结核心逻辑基于有序数组的单调性双指针单向扫描完成元素匹配计数同步计算出现次数的异或和。关键操作双指针无回溯遍历、连续相等元素计数、按位异或累加结果、大输入量IO优化。效率保障严格线性时间复杂度指针仅向右移动无重复遍历千万级数据可高效处理。代码简要说明全局数组定义开辟长度为1e710的全局数组a、b类型为unsigned long long适配大数值范围且避免栈溢出。输入加速关闭cin同步流并解绑tie大幅提升海量数据的读取速度。双指针遍历i、j分别从数组首元素开始相等则计数累加并移动j指针不等则将当前计数异或入答案移动值较小一侧的指针并重置计数。收尾处理循环结束后补充异或最后一次的计数确保无遗漏。结果输出每组数据输出最终的异或和结果。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;#defineXD114514ll t;ull a[10000010],b[10000010];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cint;while(t--){ull n,m;cinnm;for(ll i1;in;i)cina[i];for(ll i1;im;i)cinb[i];ll i1,j1,num0,ans0;while(injm){if(a[i]b[j]){num;j;}else{ans^num;if(a[i]b[j])i;elsej;num0;}}ans^num;coutansendl;}return0;}