[ARC092D] Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

难度：\(4.0\)

• Problem Statement

You are given two integer sequences, each of length \(N\): \(a_1, \cdots ,a_N\) and \(b_1, \cdots ,b_N\).

There are \(N^2\) ways to choose two integers \(i\) and \(j\) such that \(1 \leq i,j \leq N\). For each of these \(N^2\) pairs, we will compute \(a_i+b_j\) and write it on a sheet of paper. That is, we will write \(N^2\) integers in total.

Compute the XOR of these \(N^2\) integers.

给定两个长度为 \(n\) 的正整数数组 \(a,b\) ，求 \(\forall 1 \leq i,j \leq n\)，\(a_i+b_j\) 在二进制下的异或和 。

• Input

\(n\) 和两数组 \(a,b\) 。

• Output

答案。

• Sample Input

• Sample Output

• Constraints

\(1 \leq n \leq 200000\)，\(1 \leq a_i,b_j \leq 2^{28}\)。

 

 

Source：ARC092D

 

---

 

 

from orz zzx：

对每一位 \(d\)，求有多少对 \(i,j\) 满足 \(a_i+b_j\) 的第 \(d\) 位为 \(1\)，也就是 \((a_i+b_j) \bmod 2d+1 \geq 2d\)，单调性扫一扫就行了，复杂度 \(O(n(\log a_i+\log b_i))\)。

这题比我在泉州集训出的某个题略微简单一点，那个题是求所有 \(l \leq r\)
的 \(\sum\limits_{i=l}^r a_i\) 的异或和，思路类似。

 

from sb mnihyc：

「单调性扫一扫」想得不是很清楚的可以直接排序+二分。

具体来说就是：枚举位，要查找序列中有多少个数当前位为 \(1\)。

如果要查找 \(N\) 次的话，普通查找的复杂度就是 \(N^2\)。

显然我们可以通过排序优化这个操作。

将其中一个数组排序后再查找，目标就变成了有序序列中连续的单调的一段，使用二分，复杂度 \(O(n \log n)\)。