题解

思路

令前缀异或 $p_0=0$，$p_i=a_1\oplus\cdots\oplus a_i$。子数组 $[l,r]$ 对应前缀下标 $i=l-1<j=r$，异或值为 $p_i\oplus p_j$，长度为 $j-i$。

做法

小规模可枚举左端点并向右维护异或值，复杂度 $O(n^2)$。

若所有元素均为 $x$，奇数长度子数组异或为 $x$，偶数长度为 0，枚举奇数长度并累加 $x\cdot len\cdot(n-len+1)$ 即可。

一般情况逐位计算。扫描右前缀下标 $j$ 时，对某一位记录此前该位为 0/1 的前缀数量 count 及下标和 sumIndex。只有位值相反的前缀 $i$ 有贡献，其距离和为

乘该位权并累加，再把当前前缀加入统计。

正确性证明

每个子数组与唯一前缀对 $i<j$ 一一对应，且长度恰为 $j-i$。异或值可按二进制位线性拆分；某位在 $p_i,p_j$ 不同时贡献该位权，否则贡献零。扫描 $j$ 时，公式精确求出了所有此前异值前缀的距离之和，因此每个前缀对在每一位恰被累计一次。所有位求和即为原目标。

复杂度分析

处理 31 个二进制位，时间复杂度 $O(31n)$，空间复杂度 $O(31)$。