NC18979 毒瘤xor

题目要求 最大，涉及到异或操作，很显然我们需要用位运算来处理这题

思路：
位运算时，每一个bit可以被独立的拿出来运算，所以我们记X的第p位bit为 ，区间里 的第p位bit为 ，看看怎么让区间里 最大，也就是让区间里第p位bit上出现1的次数最多。
二进制中每一个bit不是0就是1，我们又知道异或运算 、 、 ，想让一个bit变成1，那么参与运算的两个bit必须是一个0和一个1，区间里都是固定的，所以我们需要改变。
结合题目说明 “若有多组可行解，请输出较小的解”
这样我们就可以推断出:

• 当区间里第p位上1的数量大于0时，令
• 当区间里第p位上1的数量等于0时，令 ，（输出较小的解）
• 当区间里第p位上1的数量小于0时，令

这样对每一个处理完以后，就得到了符合题意的

当然，如果每一次询问都数一下出现了多少次1的话计算量 可能 有点大，所以下面用了前缀和

*把DEBUG改成1会输出nums和bit

#include <iostream>
#include <memory.h>
#include <algorithm>

#define DEBUG 0
using namespace std;

int main() {
    int N;  //序列长度
    cin >> N;
    int nums[N + 1];  //a1~aN
    int bit[N + 1][33];   //a1~aN的二进制各个位中1出现的次数（从右往左数）
    memset(nums, 0, sizeof(nums));
    memset(bit, 0, sizeof(bit));
    for (int i = 1; i <= N; ++i) {
        cin >> nums[i];
        for (int j = 0; j <= 31; ++j) {
            bit[i][j + 1] = bit[i - 1][j + 1];
            if (nums[i] & (1 << j))bit[i][j + 1]++;
        }
    }
    //输出nums
    if (DEBUG) {
        cout << "nums: ";
        for (int i = 1; i <= N; ++i) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }
    //输出bit
    if (DEBUG) {
        cout << "bit: " << endl;
        for (int i = 0; i <= N; ++i) {
            cout << "[" << i << "]: ";
            for (int j = 32; j >= 1; --j) {
                cout << bit[i][j] << " ";
            }
            cout << "( " << nums[i] << " )" << endl;
        }
        cout << endl;
    }

    int q;  //询问的次数
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int L, R;    //区间端点（闭区间）
        cin >> L >> R;
        int X = 0;    //解
        for (int j = 31; j >= 1; --j) {
            if (bit[R][j] - bit[L - 1][j] < (R - L + 1) / 2.0) {
                X += (1 << (j - 1));
            }
        }
        cout << X << endl;
    }
}