2022河南萌新联赛第（七）场：南阳理工学院 F-数对

F-数对_2022河南萌新联赛第（七）场：南阳理工学院 (nowcoder.com)

题意：

思路：这道题和牛客挑战赛A题很像：A-Pair_牛客挑战赛62 (nowcoder.com)

唯一的区别是这题给多个询问，统计区间内满足条件的数的对数

首先，两个数与的结果大于等于两个数异或的结果，结论就是这两个数最高位相同

其实仔细想想也能把结论想出来：

两个数与的结果要大于异或的结果，说明与的结果的highbit大于异或结果的highbit

因此这两个数的highbit相同

那么问题就变成询问区间内相同highbit的数的个数，然后C(x,2)就是答案了

那这样只需前缀和维护一下，快速查询即可

Code：

#include 
using namespace std;
const int mxn=1e5+10;
#define int long long
int n,m,l,r,ans=0;
int a[mxn],s[mxn][31],zero[mxn];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(!a[i]){zero[i]++;continue;}
		for(int j=30;j>=0;j--){
			if((a[i]>>j)&1){s[i][j]=1;break;}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=30;j>=0;j--) s[i][j]+=s[i-1][j];
		zero[i]+=zero[i-1];
	}
	/*for(int i=1;i<=n;i++){
		for(int j=30;j>=0;j--) printf("%d",s[i][j]);
		printf("\n");
	}*/
	while(m--){
		ans=0;
		scanf("%lld%lld",&l,&r);
		for(int j=30;j>=0;j--){
			int cnt=s[r][j]-s[l-1][j];
			ans+=cnt*(cnt-1)/2;
		}
		int cnt=zero[r]-zero[l-1];
		ans+=(cnt-1)*cnt/2;
		printf("%lld\n",ans);
	}
	return 0;
}

总结：

1.对于int类型，遍历二进制位从30遍历到0

对于long long类型，就是63遍历到0

2.求对的数量就用C(x,2)，即(x-1)*x/2

3.对位运算问题，要从二进制位角度去思考问题