[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)$。