You are given a sequence A1, A2, ..., AN and Q queries. In each query, you are given two parameters L and R; you have to find the smallest integer X such that 0 ≤ X < 231and the value of (AL xor X) + (AL+1 xor X) + ... + (AR xor X) is maximum possible.
Note: xor denotes the bitwise xor operation.
For each query, print a single line containing one integer — the minimum value of X.
Subtask #1 (18 points):
Subtask #2 (82 points): original constraints
Input:
5 3
20 11 18 2 13
1 3
3 5
2 4
Output:
2147483629
2147483645
2147483645
感觉codechef easy里面的都是智商题啊qwq。。
这题我们可以按位考虑。
如果当前为二进制下第$i$位,区间$(l, r)$中元素第$i$位含有$1$的有$x$个
很显然,当$x <= \frac{r - l + 1}{2}$时$0$的个数多,那么答案的第$i$位应为$1$,否则为$0$
#include<cstdio>
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, Q;
int a[MAXN], sum[32][MAXN];
main() {
N = read(); Q = read();
for(int i = 1; i <= N; i++) a[i] = read();
for(int j = 0; j <= 30; j++)
for(int i = 1; i <= N; i++)
sum[j][i] = sum[j][i - 1] + ((a[i] & (1 << j)) != 0);
while(Q--) {
int l = read(), r = read(), ans = 0;
for(int i = 0; i <= 30; i++)
if(2 * (sum[i][r] - sum[i][l - 1]) < (r - l + 1))
ans |= (1 << i);
printf("%lld\n", ans);
}
}