本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-22 14:28:39

题意

定义 $f(l,r)$ 为 $a_l$ 到 $a_r$ 的异或和，三元组 $(x,y,z)$ 合法当且仅当 $1\le x\le y\le z\le n$，且 $f(x,y)\oplus f(y,z)>f(x,z)$，求合法三元组的个数。

思路

展开式子，得到 $f(x,y)\oplus f(y,z)=f(x,z)\oplus a_y$，考虑枚举每个 $i$ 作为 $y$ 的贡献，问题转化为求满足 $x\le y\le z$ 且 $f(x,z)\oplus a_y>f(x,z)$ 的二元组 $(x,z)$ 数量。

考虑 $f(x,z)$ 要怎样才能异或上 $a_y$ 后变大。发现若 $a_y$ 二进制下最高位为第 $k$ 位，则 $f(x,y)$ 的第 $k$ 位为 $0$ 即合法，否则不合法。

考虑证明，显然 $a_y$ 最高位的值一定大于 $\frac{a_y}{2}$，所以 $f(x,z)$ 异或 $a_y$ 后，第 $k$ 位增加的值一定比后面的位总共减少的值大，结果一定增加；反之也一样。

那么需要快速求出某一位为 $0$ 的 $f(x,z)$ 数量，考虑使用前缀和。设 $b_i$ 为 $a_1$ 至 $a_i$ 的异或和，那么 $f(x,z)=b_{x-1}\oplus b_z$。特别地，有 $b_0=0$。

如此 $f(x,z)$ 第 $k$ 位为 $0$ 就转化为 $b_{x-1}$ 和 $b_z$ 的第 $k$ 位相同。因此再设 $s_{i,j}$ 表示 $b_0$ 到 $b_i$ 中第 $j$ 位为 $1$ 的个数，这样用乘法原理即可快速求出合法的 $(x,z)$ 个数。

代码

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int N=1e5+10;
const int K=30+10;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int T,n,ans,a[N],b[N],s[N][K],h[N];\/\/h[i]表示a[i]的最高位，其余如上述 
signed main()
{
	T=read();
	while(T--)
	{
		n=read(),ans=0;
		for(int i=1;i<=n;i++) a[i]=read(),b[i]=b[i-1]^a[i],h[i]=floor(log2(a[i]));
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=30;j++) s[i][j]=s[i-1][j];
			int ct=0;
			while(b[i])
			{
				if(b[i]&1) s[i][ct]++;
				b[i]>>=1,ct++;
			}
		}\/\/按思路维护各数组 
		for(int i=1;i<=n;i++) 
		{
			int ta=s[i-1][h[i]],tb=s[n][h[i]]-s[i-1][h[i]];\/\/b[x-1]与b[z]同为1的数量 
			int tc=i-ta,td=n-i+1-tb;\/\/同为0的数量，注意x=1时b[0]也要考虑进去 
			ans+=ta*tb+tc*td;\/\/统计方案数 
		}
		cout<<ans<<'\n';
	}
	return 0;
}