题面

解题思路

这里提供一种乱搞新奇的算法（完全在线鬼知道有什么用

分析

考虑拆位，由于异或的性质（算是吧，不同位之间不影响，因此可以计算每个位做出的贡献，然后累加

显然，只有奇数个 $1$ 才能做出贡献，所以我们只要能计算出有多少个区间包含奇数个 $1$

尝试看看有什么规律：

数 $2$ $5$ $6$
$2^2$ $0$ $1$ $1$
$2^1$ $1$ $0$ $1$
$2^0$ $0$ $1$ $0$

对 2,5,6 分别拆位，表示为上述的表（当然做的时候没必要记录

考虑 $2^2$，以第 $1$ 个数 $2$ 为区间右端点，有贡献的区间有 $0$ 个；以第 $2$ 个数 $5$ 为区间右端点，有贡献的区间有 $[1,2]$ 和 $[2,2]$ 共 $2$ 个；以第 $3$ 个数 $6$ 为区间右端点，有贡献的区间有 $[3,3]$ 共 $1$ 个。做出的总贡献为 $(2+1)\times 2^2$

其余位同理

不难看出，如果将序列按 $1$ 的位置分段，则右端点处于某段中（即为 $0$ 的情况）时，有贡献的区间数为与之距离奇数段的区间总跨度；为某段的右端点（即为 $1$ 的情况）时，贡献为与之距离偶数段的区间总跨度，$Rt$

  • 在一个某段中（即为 $0$ 的情况），

    $7,8$ 等，贡献即为其之前蓝色区间的跨度 $6-4=2$

    $10,11$ 等，贡献即为其之前红色区间的跨度 $(9-6)+(4-0)=7$

  • 为某段的右端点（即为 $1$ 的情况），

    $4$ 等，贡献即为其之前红色区间的跨度 $4-0=4$

    $12$ 等，贡献即为其之前蓝色区间的跨度 $(12-9)+(6-4)=5$

然后我们就可以得出这样一个代码：

int n,k,sum[31][2],p[31],pos[31];LL ans,c;
int main()
{
    rint i,j;n=read();
    for(i=1;i<=n;i++) {
        k=read(),c=1;
        for(j=0;j<30;++j,c<<=1) {//pos记录上一个1的位置，sum[_][0/1]记录红蓝色区间分别的跨度
            if(k&c) p[j]^=1,sum[j][p[j]]+=i-pos[j],pos[j]=i;
            ans+=sum[j][p[j]]*c;//累加贡献
        }
    }
    printf("%lld",ans);
    return 0;
}

more

但是，还可以优化，由于做到 $1$ 时，红蓝色区间跨度之和定等于 $i$，又做到 $0$ 时，对红蓝色区间的跨度无影响，因此可以改成：

    rint i,j;n=read();
    for(i=1;i<=n;i++) {
        k=read(),c=1;
        for(j=0;j<30;++j,c<<=1) {//红蓝区间的跨度可以由另外一个推得
            if(k&c) sum[j]=i-sum[j];
            ans+=sum[j]*c;
        }
    }

或者我们还可以这样考虑：由于异或具有自反性，因此可以考虑拆位后求出异或前缀，这样的话有贡献的区间即为 $1$ 的个数与 $0$ 的个数之积

rint i,j;n=read();
for(i=1;i<=n;i++) {
    k=read(),c=1;
    for(j=0;j<30;++j,c<<=1)
        p[j]^=k&c,++sum[j][p[j]];//分别存前缀异或，以及1和0的个数
}
for(i=0,c=1;i<30;++i,c<<=1) ans+=sum[i][0]*sum[i][1]*c;

warning

$\mathtt{non}$

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,k,sum[31];LL ans,c;
int main()
{
    rint i,j;n=read();
    for(i=1;i<=n;i++) {
        k=read(),c=1;
        for(j=0;j<30;++j,c<<=1) {
            if(k&c) sum[j]=i-sum[j];
            ans+=sum[j]*c;
        }
    }
    printf("%lld",ans);
    return 0;
}

devil.