题意
给定两个长度为 \(n\) 的数组 \(a,b\)，求
\[\sum_{i=1}^n\sum_{j=i+1}^n\min\{a_i\oplus a_j,b_i\oplus b_j\} \]其中 \(\oplus\) 表示按位异或。
分析
简单二进制分治题（看代码可能更好理解）。
先将有序对转成无序对，最后答案为结果的一半。
考虑去除 \(\min\)，于是拆位计算贡献。
一个经典的思路是考虑 \(a_i\oplus a_j,b_i\oplus b_j\)，在第 \(k\) 位不同，凭此判断大小。设计函数 \(f(a,b,k)\) 表示 \(a_i\oplus a_j,b_i\oplus b_j\) 的第 \(k\) 位之后全部相等，计算 \(1 \rightarrow k\) 位的贡献。把每个元素视作 01 二元组 \((x,y)\)，代表 \(a_i,b_i\) 的第 \(k\) 位上的值。答案的贡献分如下几种考虑：
1.\((x,y) \leftarrow (\neg x,y)\)，这就说明 \(a_i \oplus a_j\) 这一位是 \(1\)，而 \(b_i \oplus b_j\) 这一位是 \(0\)，\(\min = b_i \oplus b_j\)，这部分记录位的就能 \(O(\log n)\) 算一个数的答案了。
2.\((x,y) \leftarrow (x,\neg y)\)，同 1 处理。
3.$(x,y) \leftarrow (\neg x,\neg y) $，两位相等，无法判断大小，但恒有 \(2^k\) 的贡献，向下递归处理。
4.$(x,y) \leftarrow (x,y) $，同 3，无贡献，直接向下递归处理。
\(O(\log V)\) 层，每层均摊 \(O(n\log V)\)，时间复杂度为超小常数 \(O(n\log^2V)\)。
代码
#include <bits/stdc++.h>
#define lb(x) (x&-x)
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
using namespace std;
using ll=long long;
using LL=__int128;
using pii=pair<ll,int>;
const int N=25e4+5; ll ans;
struct PairSet{
int c[20][2]; vector<int>v;
PairSet(){ memset(c,0,sizeof(c)); }
void ins(int x){
v.push_back(x);
for(int j=0;j<20;j++)
c[j][x>>j&1]++;
}
ll ask(int x){
ll res=0;
for(int j=0;j<20;j++)
res+=(1ll<<j)*c[j][!(x>>j&1)];
return res;
}
};
void solve(vector<int>&a,vector<int>&b,int k){
int n=a.size(); if(!n||!~k) return ;
PairSet w[2][2][2];
for(int i=0;i<n;i++){
int x=a[i]>>k&1,y=b[i]>>k&1;
w[x][y][0].ins(a[i]&=(1<<k+1)-1);
w[x][y][1].ins(b[i]&=(1<<k+1)-1);
}
for(int i=0;i<n;i++){
int x=a[i]>>k&1,y=b[i]>>k&1;
ans+=w[x][y^1][0].ask(a[i]);
ans+=w[x^1][y][1].ask(b[i]);
ans+=(ll)w[x^1][y^1][0].v.size()*(1<<k);
}
for(int i=0;i^2;i++){
for(int x:w[1][i^1][0].v) w[0][i][0].v.push_back(x);
for(int x:w[1][i^1][1].v) w[0][i][1].v.push_back(x);
solve(w[0][i][0].v,w[0][i][1].v,k-1);
}
}
int main(){
int n; scanf("%d",&n);
vector<int>a(n),b(n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<n;i++) scanf("%d",&b[i]);
return solve(a,b,20),printf("%lld",ans>>1)&0;
}