1323D

题目：传送门 

题意：求数组元素两两相加后全部异或起来的结果。

思路：暴力求和O(n^2)显然超时，因此可以考虑对所有元素对应的二进制数一位一位算答案。由于是异或，只需要知道某一位“1“”的总个数的奇偶。但是加法涉及进位，不能直接按位计数，那么我们需要把进位考虑在内。高位求和对低位是没有影响的，反之低位求和可能会进位对高位造成影响。因此可以从低位开始枚举，并且把高位给去掉（便于后续二分处理）。那么前 i 位 (从第0位开始) 的数字大小范围 [ 0，2^(i+1)-1 ]，而两个数求和后的范围为 [ 0，2^(i+2)-2 ] ,其中满足第 i 位为1的范围为 [ 2^i，2^(i+1)-1 ] U [ 2^(i+1)+2^i ，2^(i+2)-2 ] ; 因此，对去掉高位后的数组排序，求出对于ai来说，与其他元素aj相加后在“有效范围”内的aj总个数 【二分区间端点值-ai 即可】；

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const int N=4e5+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-9;
const long double pi=acos(-1.0L);
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
LL read()
{
    LL x=0,t=1;
    char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') t=-1;
    while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
    return x*t;
}
int a[N],t[N];
int main()
{
    int n=read(),ans=0;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int k=1;k<30;k++)
    {
        int lim=(1<<k)-1,sum=0;
        for(int i=1;i<=n;i++) t[i]=a[i]&lim;
        sort(t+1,t+n+1);
        for(int i=1;i<=n;i++)
        {
            sum+=(upper_bound(t+i+1,t+n+1,lim-t[i])-t)-(lower_bound(t+i+1,t+n+1,(1<<k-1)-t[i])-t);
            sum+=(upper_bound(t+i+1,t+n+1,(lim<<1))-t)-(lower_bound(t+i+1,t+n+1,(1<<k-1)+(1<<k)-t[i])-t);
        }
        if(sum&1) ans+=1<<k-1;
    }
    printf("%d
",ans);
    return 0;
}