D
https://atcoder.jp/contests/arc127/tasks/arc127_d
题目大意,(atcoder 的这个题没有“背景”，直接去看原题，就是题意
给等长数组A,B, 对于两两坐标i,j, 计算$min(A_i \oplus A_j, B_i \oplus B_j )$
求所有min的和
范围
$n \leq 250000 , A_i,B_i < 2^{18}$
想
先做一些简单的分析,N 有点大，$N^2$的话肯定超时, 那么基本范围是$N , N log(N)$ 左右的
$2^{18} = 262144$
min(x,y)+max(x,y) = x+y
一些 $\oplus$ 的常见知识, $(A \oplus B) = (A + B) \bmod 2$, 其中加和模采取 每位不进位且允许超过2的任意值, 这个好处是能计数
例如 5 = 101,7=111, 9 = 1001
$(0,1,0,1)+(0,1,1,1)+(1,0,0,1) = (1,2,1,3) $
$(1,2,1,3) \bmod 2 = (1,0,1,1) $
所以$5 \oplus 7 \oplus 9 = 11$, 同时我们知道最高位1个1，2个0
a < b 那么 $a \oplus b$ 的最高位1出现在b
反过来
$a \oplus b$ 最高位出现在b , 那么 a < b
(归纳法易证
$a \oplus (b+c+d+e+\cdots) =$ 后面部分通过上面按位不进位加和统计的每一位 0 个数 或1个数，在看与a对应位是否相等
通过前缀和或者扫描记录当前， 长度为n的数组的两两$\oplus$的和 的时间复杂度O(N) 就能完成
综上，我们可以直接算出 min， 也可以去算max然后拿总和减去min
算法
把所有数看成18位，不足高位补零
我们 关心$(A_i \oplus A_j) \oplus (B_i \oplus B_j) $ 的最高位的bit从哪里来，这样我们就知道哪个最大了
$(A_i \oplus A_j) \oplus (B_i \oplus B_j) = (A_i \oplus B_i) \oplus (A_j \oplus B_j) $
令$C_i = A_i \oplus B_i$
w = 18
把$C_i$分类成两组, 一组是 第$w$位为$1$的，另一组是$w$位为$0$的
每组内，循环这个方法并且w-1
对于组之间的，
$C_i$的$w$位为1, $C_j$的$w$位为0 , 对于高于w位的，因为通过上面的分治，两边保持一致，也就是$\oplus$以后都是0了不需要考虑
对于$w$位为1 里面我们还可以分类为 $A_i$ 的w位是0或1两类
$G_{x,y}$ w位是x，A的w位是y
$G_{1,0},G_{0,0}$, 高位1来自B的$\oplus$
$G_{1,0}, G_{0,1}$, 高位1来自A的$\oplus$
$G_{1,1}, G_{0,0}$, 高位1来自A的$\oplus$
$G_{1,1}, G_{0,1}$, 高位1来自B的$\oplus$
也就是分组的时间复杂度就是$2^L$
下面考虑
$G_{i_0,i_1,i_2,\cdots} $ 与 $G_{j_0,j_1,j_2,\cdots}$ 中 如果高位来自A的$\oplus$
那么贡献为
$ \sum B_{i_?} \oplus B_{j_?}$
也就是，上面想求总和提到过的方法, 通过按位计数，拿着一块求和的单个复杂度为$O(L\cdot size(G))$, 总复杂度为$O(L\cdot N)$
然后注意处理$C_i$ 一致的组，这样的组里面，两两的异或值相同, 也需要上面的按位计数的求和
Code
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
int A[250010];
int B[250010];
const int L = 18;
ll xorSum(vector<int> & i0){
if(i0.size() == 0)return 0;
vector<int> bits = vector<int>(20,0);
ll ans = 0;
rep(i,0,i0.size()){
if(i > 0){
rep(b,0,L){
ans += ((A[i0[i]]>>b) % 2)?
((ll)1 << b) * (i - bits[b]):
((ll)1 << b) * (bits[b]);
}
}
rep(b,0,L){
bits[b]+=(A[i0[i]]>>b)%2;
}
}
return ans;
}
ll xorSum(vector<int> & i0,vector<int> & i1, int * Arr){
if(i0.size() == 0 || i1.size() == 0)return 0;
vector<int> bits = vector<int>(20,0);
rep(i,0,i0.size()){
rep(b,0,L){
bits[b]+=(Arr[i0[i]]>>b)%2;
}
}
ll ans = 0;
rep(i,0,i1.size()){
rep(b,0,L){
ans += ((Arr[i1[i]]>>b) % 2)?
((ll)1 << b) * (i0.size() - bits[b]):
((ll)1 << b) * (bits[b]);
}
}
return ans;
}
ll f(int pwr,vector<int> & idxs){
if(pwr < 0){
return xorSum(idxs);
}
vector<int> gC[2] = {{},{}};
vector<int> gCA[2][2] = {{{},{}},{{},{}}};
for(auto i:idxs){
int C = A[i]^B[i];
gC[(C>>pwr)%2].pb(i);
gCA[(C>>pwr)%2][(A[i]>>pwr)%2].pb(i);
}
ll ans = 0;
rep(i,0,2){
if(gC[i].size() < 2) continue;
ans += f(pwr-1,gC[i]);
}
rep(bA0,0,2){
rep(bA1,0,2){
ans += (bA0 ^ bA1)?
xorSum(gCA[0][bA0],gCA[1][bA1], B):
xorSum(gCA[0][bA0],gCA[1][bA1], A);
}
}
return ans;
}
int main(){
int n;
cin>>n;
rep(i,0,n){
scanf("%d",A+i);
}
rep(i,0,n){
scanf("%d",B+i);
}
vector<int>idxs;
rep(i,0,n){
idxs.pb(i);
}
printf("%lld",f(L,idxs));
return 0;
}
|
Ref
https://atcoder.jp/contests/arc127/editorial/2697