[每日一题] [NC18979] 毒瘤xor

题目大意：有一个数组，每次询问数组的第L个到第R个数和某个数x的xor的总和最大的那个x。

https://ac.nowcoder.com/acm/problem/18979

其实很简单，没个bit可以分开，那么就是要么这个bit不变，要么全部flip，问哪种剩下的1个数多，只要能飞快地知道这一位0和1的个数就知道该不该flip了。用一个前缀和就可以存[0, R]的1的个数，那么就很容易知道[L, R]的1的个数，0的个数就是(R - L + 1)减去1的个数。

int N;
#define MAXN 100005
int a[MAXN];
int Q;
int L, R;
#define MAXH 31
int counter[MAXN][MAXH];
int doit(int L, int R) {
  int tot = R - L + 1;
  int ans = 0;
  for (int h = 0; h < MAXH; ++h) {
    int one_count = counter[R][h] - (L ? counter[L - 1][h] : 0);
    int zero_count = tot - one_count;
    if (one_count < zero_count) {
      ans |= (1 << h);
    }
  }
  return ans;
}
int main(int argc, char* argv[]) {
  read(N);
  read(a, N);
  for (int h = 0; h < MAXH; ++h) {
    for (int i = 0; i < N; ++i) {
      if (i) counter[i][h] = counter[i - 1][h];
      if (a[i] & (1 << h)) {
        counter[i][h]++;
      }
    }
  }
  read(Q);
  REP(q, Q) {
    read(L, R);
    --L,--R;
    print(doit(L, R));
  }
  return 0;
}