DDOSvoid's Blog

Luogu T51127 SDSCD6T2 B

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/T51127

简要题意：给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$，求 $\forall i\in[1,n],j\in[1,n],a_i+b_j$​ 的异或和

$n\le 2\times 10^5$

Solution

按位考虑，我们只需要知道这 $n^2$ 个值有奇数还是偶数个 $1$ 即可

不妨假设我们现在正在考虑第 $k$ 位，那我们将两个数组对 $2^{k+1}$ 取模，因为更高的位是没用的

那么我们发现有 $1$ 的情况如下

$2^k\le a_i+b_j<2^{k+1},2^{k}+2^{k+1}\le a_i+b_j$

排序双指针即可，时间复杂度 $O(n\log ^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cctype>
#define maxn 200010
#define gc getchar
using namespace std;

int read() {
    int x = 0, f = 0; char c = gc();
    while (!isdigit(c)) f |= c == '-', c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x;
} 

int n, m, a[maxn], b[maxn];

int A[maxn], B[maxn];

int ans;
int main() { 
    cin >> n;
    for (int i = 1; i <= n; ++i) a[i] = read(); 
    for (int i = 1; i <= n; ++i) b[i] = read(); 
    for (int o = 28; ~o; --o) {
        for (int i = 1; i <= n; ++i) {
            A[i] = a[i] & (1 << o + 1) - 1;
            B[i] = b[i] & (1 << o + 1) - 1;
        }
        sort(A + 1, A + n + 1, greater<int>()); sort(B + 1, B + n + 1);
        int l1 = 1, r1 = 0, r = 1, s = 0;
        for (int i = 1; i <= n; ++i) {
            while (l1 <= n && B[l1] + A[i] < (1 << o)) ++l1;
            while (r1 < n && B[r1 + 1] + A[i] < (1 << o + 1)) ++r1;
            while (r <= n && B[r] + A[i] < (1 << o) + (1 << o + 1)) ++r;
            s += (r1 - l1 + 1) + (n - r + 1); 
        }
        if (s & 1) ans += 1 << o; 
    } cout << ans << endl; 
    return 0;
}