牛客竞赛 NC18979 毒瘤xor

传送门 $\looparrowright$

题目描述

小 $a$ 有 $n$ 个数 $a_1, a_2, ..., a_n$，给出 $q$ 个询问，每次询问给出区间 $[l, r]$，现在请你找到一个数 $x$，使得 $\sum\limits_{i = l}^r x \oplus a_i$最大，要保证 $0 \le x < 2^{31}$。

输入描述

第一行一个整数 $n$，表示序列的长度。第二行 $n$ 个整数，表示序列内的元素。第三行一个整数 $q$，表示询问的个数。接下来 $q$ 行，每行两个整数 $l,r$，表示询问的区间。

输出描述

输出 $q$ 行，每行一个整数表示答案。若有多组可行解，请输出较小的解。

示例1

输入

5
4 78 12 1 3
3
2 5
1 4
3 3

输出

2147483632
2147483635
2147483635

备注

对于 $30\%$ 的数据，$n, q ≤ 10$。对于 $60\%$ 的数据，$n, q ≤ 1000$。对于 $100\%$ 的数据，$n, q ≤ 10^5$。保证 $a_i$$ <$ $2^{31}$。

分析

将所有数拆成 $31$ 位二进制数。对于一个区间 $[l,r]$，若 $x $ 的第 $j$ 位为 $1$，且 $[l,r]$ 内第 $j$ 位为 $0$ 的数字个数为 $seg_0$，那么对和式 $\sum\limits_{i = l}^r x \oplus a_i$ 产生的贡献为 $seg_0\times 2^j$；同理，若 $x$ 的第 $j$ 位为 $0$ ,且 $[l,r]$ 内第 $j$ 位为 $1$ 的数字个数为 $seg_1$，那么对和式 $\sum\limits_{i = l}^r x \oplus a_i$ 产生的贡献为 $seg_1\times 2^j$。
$seg_0\times 2^j>seg_1\times 2^j$ 的充要条件是 $seg_0>seg_1$。每次询问一个区间 $[l,r]$，我们依次考察 $[l,r]$ 内所有数的第 $0\sim 30$ 位，若某一位 $0$ 居多，则 $x$ 在该位取 $1$；否则，$x$ 在该位取 $0$。
显然，可以预处理某一位 $1$ 个数的前缀和，考察一个区间时，可以 $O(1)$ 得到答案。

代码

#include<iostream>
#include<cstdio>
#define N 100003
using namespace std;
//------------------------------
//代表[1,i]的数字第j位为1的数字个数
int sum[N][32];
//------------------------------
int q;
int n;
int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++) 
	{
		int temp;
		scanf("%d",&temp);
		for(j=0;j<=30;j++)
		{
			if(temp&(1<<j)) sum[i][j]=1;//第j位为1
			else sum[i][j]=0;//第j位为0
		}
	}
	for(i=1;i<=n;i++)//计算前缀和
	{
		for(j=0;j<=30;j++)
		{
			sum[i][j]+=sum[i-1][j];
		}
	}
	cin>>q;
	while(q--)
	{
		int l,r;
		int x=0;
		scanf("%d%d",&l,&r);
		for(j=0;j<=30;j++)
		{
			int seg1=sum[r][j]-sum[l-1][j];//第j位为1的个数
			int seg0=r-l+1-seg1;//第j位为0的个数
			//若0的个数多，该位取1。
			if(seg0>seg1) x=x+(1<<j);
		}
		printf("%d\n",x);
	}
	return 0;
}