[ARC092D] Two Sequences

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

 

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注