[CC-XXOR]Chef and Easy Problem

[CC-XXOR]Chef and Easy Problem

题目大意：

给你一个长度为(n(nle10^5))的序列(A(A_i<2^{31}))。(m(mle10^5))次询问，每次给定一个区间([l,r])，求使得(sum_{i=l}^r(A_ioplus x))最大的(x(x<2^{31}))是多少。

思路：

按位考虑，如果这一位是(1)的数比较多那么就把(x)的这一位弄成(0)，否则弄成(1)。

源代码：

#include<cstdio>
#include<cctype>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=1e5+1,B=31;
int a[N];
int sum[N][B];
int main() {
	const int n=getint(),q=getint();
	for(register int i=1;i<=n;i++) {
		const int x=getint();
		for(register int j=0;j<B;j++) {
			sum[i][j]=sum[i-1][j];
			if((x>>j)&1) sum[i][j]++;
		}
	}
	for(register int i=0;i<q;i++) {
		const int l=getint(),r=getint(),len=r-l+1;
		int x=0;
		for(register int i=0;i<B;i++) {
			if((sum[r][i]-sum[l-1][i])*2<len) x|=1<<i;
		}
		printf("%d
",x);
	}
	return 0;
}