CF1322B Present 题解
题目链接：CF1322B Present
题意：
给出一个长度为 $n$ 的数列 $a$。其中第 $i$ 项为 $a_i$。
请你求出 $\bigoplus_{i=1}^{n}\bigoplus_{j=i+1}^{n}(a_i+a_j)$。其中 $\oplus$ 表示按位异或操作。
$2 \leq n \leq 4 \times 10^5$，$1 \leq a_i \leq 10^7$。
输入格式：
The first line contains a single integer $n$ — the number of integers in the array.
The second line contains integers $a_1, a_2, \ldots, a_n$ .
输出格式：
Print a single integer — xor of all pairwise sums of integers in the given array.
注意到 $a_i \le 10^7$ ，因此二进制的位数 $\in [0, 25]$，于是依次考虑每一位的贡献。
显然，如果我们要计算两个数的和的第 $i$ 位是否为 $1$ ，至少需要这两个数前 $i$ 位的信息
不妨预处理出每个数 $a_j$ 在 $i$ 相同时前 $i$ 位所对应的数，记为 $b_j$ 。
如果 $b_x+b_y$ 的第 $i$ 位为 $1$ ，则
- 第 $i$ 位没有进位，则 $b_x + b_y \in [2^i,~2^{i+1}-1]$ 。
- 第 $i$ 位进位了，但第 $i-1$ 位也进位了，则 $b_x + b_y \in [2^{i+1} + 2^i,~(2^{i+1}-1)\times 2]$ 。
那么知道这个范围有什么用处呢？
通常我们要数有多少个数在区间 $[l,r]$ 内，我们可以用 $[1,r]$ 的答案减去 $[1,l)$ 的答案。
于是，对于一个固定的 $b_x$ ，我们只需要找到有多少个 $b_y$ 满足 $b_x + b_y$ 小于等于某个数
可以发现，当 $b$ 内的每个数都从小到大排序时，我们倒序枚举 $b_x$ ，那么 $b_y$ 可以用一个指针来线性维护
不过最后我们要的答案是他们的异或值，不是个数，这个显然可以通过数目的奇偶性判断。
时间复杂度 $\mathcal{O}(n \log V)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e5 + 15))
int n, res, a[N], b[N];
bool check(int x, int y)
{
if(x > y) return 0;
int num = 0;
for(int i = n, l = 1, r = 1; i; i--)
{
while(l <= n && b[i] + b[l] < x) ++l;
while(r <= n && b[i] + b[r] <= y) ++r;
num += r - l - (l <= i && i < r);
}
return (num >> 1) & 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 0; i <= 25; i++)
{
for(int j = 1; j <= n; j++) b[j] = a[j] & ((1 << (i + 1)) - 1);
sort(b + 1, b + 1 + n);
int tmp = check(1 << i, (1 << (i + 1)) - 1) ^ check(3 << i, (1 << (i + 2)) - 2);
res += tmp * (1 << i);
}
cout << res << '\n';
return 0;
}参考文献：
