题解 | #毒瘤xor#

这道题思路就是，预处理前i个数字，二进制位上的1的总数。

因为要求找到一个x对区间内的a[i]做异或操作，使得异或后的区间和最大，而异或运算是这样的0^1=1 0^0=0 1^1=0，我们要想使得区间和最大，显然要让每一个位上的1的数量最大化，所以当1的数量比0少时，就对该位异或1，把0，1数量交换。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int n,q;
int sum[N][40];	//前i个数，各个位上有几个1 

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=0;i<31;i++){
		for(int j=1;j<=n;j++){
			sum[j][i]=sum[j-1][i];
			if(((a[j]>>i)&1)==1){
				sum[j][i]++;
			}
		}
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int ans=0;
		int l,r;
		cin>>l>>r;
		for(int j=0;j<31;j++){
			if(2*(sum[r][j]-sum[l-1][j])<(r-l+1)){
				ans|=(1<<j);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}