Problem

Description

给定n个数的数组A和数组B，求所有A[i]+B[j]的异或和(1<=i,j<=n)。n<=200000。

Input

n

$a_1,a_2…a_n$

$b_1,b_2…b_3$

Output

Print the result of the computation.

Sample Input

6
4 6 0 0 3 3
0 5 6 5 0 3

Sample Output

8

HINT

$n<=200000$

Solution

Analysis

考虑低位对高位的贡献。

对于某一位$k$，考虑什么情况下$a_i+b_j$对这位产生贡献。

显然的事实是如果$a_i+b_j$​对$k$产生了贡献，那么只会低位对高位产生贡献即：

$base=(1<<(k+1))-1$

只需考虑$a_i\&base$​和$b_i\&base$​对$k$这位的贡献。

显然的是$max(a_i+b_j)=(base<<1)$​，即$a_i+b_j$的最高位不会大于$k+1$；

考虑什么时候不产生贡献：

(1) $a_i+b_j < (1<<k)$

(2) $(1<<(k+1))\le a_i+b_j <(1<<(k+1)+(1<<k))$

对每层${b}$按照${b\&base}$排序，对于每个$a_i$产生的贡献即为

$A$:$a_i+b_j\ge(1<<k)$

$B$:$(1<<(k+1))\le a_i+b_j <(1<<(k+1)+(1<<k))$

$sum=A-B$

Attention

注意二分边界

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define il inline
typedef long long ll;
using namespace std;
il int read(){ int x;scanf("%d",&x);return x;}
const int N=200010;
ll a[N],b[N],c[N];int n;

il ll find(ll x,ll v){
    v-=x;
    int l=1,r=n,res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(c[mid]>=v){ res=mid;l=mid+1;}
        else r=mid-1;
    }
    return res;
}

int main(){
    n=read();
    rep(i,1,n) a[i]=read();
    rep(i,1,n) b[i]=read();
    ll ans=0;
    rep(k,1,29){
        ll base=(1<<k)-1,sum=0;
        rep(i,1,n) c[i]=(b[i]&base);
        sort(c+1,c+1+n,greater<ll>());
        rep(i,1,n) sum+=find(a[i]&base,(1<<(k-1)));
        rep(i,1,n) sum-=find(a[i]&base,(1<<k))-find(a[i]&base,(1<<k)+(1<<(k-1)));
        if(sum&1) ans+=(1<<(k-1));
    }
    printf("%lld\n",ans);
    return 0;
}