题目描述
难度分:1900
输入T(≤104)表示T组数据。所有数据的n之和≤105。
每组数据输入n(1≤n≤105)和长为n的数组a(1≤a[i]≤109)。
定义S(i,j)为a[i]⊕a[i+1]⊕…⊕a[j],即子数组的异或和。
输出有多少个i,j,k满足i≤j≤k且S(i,j)⊕S(j,k)>S(i,k)。
输入样例
3
3
6 2 4
1
3
5
7 3 7 2 1
输出样例
4
0
16
算法
前后缀分解
假设s[i]=⊕j∈[1,i]a[j],根据前缀和的性质,要找的其实是满足s[k]⊕s[x−1]<s[k]⊕s[x−1]⊕a[j]的三元组(i,j,k)。令T=s[k]⊕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∈[1,n],对每个i要遍历所有的位,所以时间复杂度为O(nlog2U),其中U为值域,本题U=109。然后枚举j,同样需要遍历a[j]每个位来确定最高位的1,时间复杂度还是O(nlog2U)。
空间复杂度
空间消耗主要在于异或和每位1个数的前缀和数组s,空间复杂度为O(nlog2U),这也是整个算法的额外空间复杂度(其实也可以优化掉这个空间,但是有个前缀和数组更无脑一些)。
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;
}