题目描述

难度分:$1900$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

定义$S(i,j)$为$a[i] \oplus a[i+1] \oplus … \oplus a[j]$，即子数组的异或和。

输出有多少个$i,j,k$满足$i \leq j \leq k$且$S(i,j) \oplus S(j,k) \gt S(i,k)$。

输入样例

3
3
6 2 4
1
3
5
7 3 7 2 1

输出样例

4
0
16

算法

前后缀分解

假设$s[i]=\oplus_{j \in [1,i]} a[j]$，根据前缀和的性质，要找的其实是满足$s[k] \oplus s[x-1] \lt s[k] \oplus s[x-1] \oplus a[j]$的三元组$(i,j,k)$。令$T=s[k] \oplus s[x-1]$，易知$T$能不能变大取决于$a[j]$为$1$的位，直接贪心找到$a[j]$的最高位$1$，只要这一位异或到$T$上能够把$T$对应位的$0$变成$1$就可以了。那也就是说需要$s[k]$和$s[x-1]$在这一位是$0$，则要么$s[k]$和$s[x-1]$在这一位都是$1$，要么在这一位都是$0$。

因此，可以做个预处理，预处理出一个每位的前缀和数组，$presum[b][i]$表示的是第$b$位，$s$的前缀$[1,i]$上有多少个$1$。当枚举$a[j]$时，假设$k$是$a[j]$最高为$1$的位，$[1,j]$和$[j,n]$上都是$1$的数交叉组合+$[1,j]$和$[j,n]$上都是$0$的数交叉组合（用乘法原理）起来就是$a[j]$对答案的贡献，所有$a[j]$的贡献累加起来就是答案。

复杂度分析

时间复杂度

预处理出每一位$1$的前缀和，需要遍历$i \in [1,n]$，对每个$i$要遍历所有的位，所以时间复杂度为$O(nlog_2U)$，其中$U$为值域，本题$U=10^9$。然后枚举$j$，同样需要遍历$a[j]$每个位来确定最高位的$1$，时间复杂度还是$O(nlog_2U)$。

空间复杂度

空间消耗主要在于异或和每位$1$个数的前缀和数组$s$，空间复杂度为$O(nlog_2U)$，这也是整个算法的额外空间复杂度（其实也可以优化掉这个空间，但是有个前缀和数组更无脑一些）。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010;
int T, n, a[N], eor[N], s[30][N];

void solve() {
    // s[k]^s[i-1] < s[k]^s[i-1]^a[j]
    LL ans = 0;
    for(int j = 1; j <= n; j++) {
        int k = 29;
        while(k >= 0 && !(a[j]>>k&1)) k--;
        if(k == -1) continue;
        ans += 1LL*(s[k][n] - s[k][j - 1])*s[k][j - 1];
        ans += 1LL*(n - j + 1 - (s[k][n] - s[k][j - 1]))*(j - s[k][j - 1]);
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            eor[i] = eor[i - 1] ^ a[i];
            for(int j = 0; j < 30; j++) {
                s[j][i] = s[j][i - 1] + (eor[i]>>j&1);
            }
        }
        solve();
    }
    return 0;
}