自动搬运

查看原文

来自洛谷，原作者为

	Butterfly_qwq 最后在线时间：2025年8月24日22时0分

搬运于2025-08-24 23:01:53，当前版本为作者最后更新于2024-08-10 19:17:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单题。

考虑什么时候会满足条件，设 $a_i<a_j$。

现在 $a_i$ 和 $a_j$ 的最高位不能相同，否则，$a_i\oplus a_j<a_i$。

然后 $a_i$ 的最高位在 $a_j$ 中必须是 $1$，否则 $a_i\oplus a_j>a_j$。

显然只需统计满足这些条件的数目就行了。枚举 $i$，看有多少个 $j$ 满足条件，具体直接维护两个数组，一个是有多少个数满足最高位是定值，一个是有多少数的第定值位是 $1$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,ans,a[500005],hb[500005],ct1[500005],ct2[500005];
int highbit(int x)
{
	if(!x)return 114514;
	for(int j=30;~j;j--)if(x&(1<<j))return j;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--)
	{
		memset(ct1,0,sizeof(ct1));
		memset(ct2,0,sizeof(ct2));
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)
		{
			hb[i]=highbit(a[i]);
			ct2[hb[i]]++;
			for(int j=30;~j;j--)if(a[i]&(1<<j))ct1[j]++;
		}ans=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i])ans+=ct1[hb[i]]-ct2[hb[i]];
			else ans+=n;
		}
		cout<<ans<<'\n';
	}
}