题目:

小a有N个数a1, a2, ..., aN,给出q个询问,每次询问给出区间[L, R],现在请你找到一个数X,使得
1、

2、最大,表示异或操作。


做法:

由于异或位于位之间是不影响的,所以我们可以分别考虑X每个位选0还是选1。若[L,R]区间的数中第i位,0的数量>1的数量,则X的第i位选1比0优。反之,选0比选1优。
所以通过前缀和处理,快速得到[L,R]区间中的数每个位的1的数量,然后每个位贪心选0或1,问题解决。


代码:

#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int a[N], cnt[N][35];
int solve(int l, int r){
    int len = r-l+1, ans = 0;
    for (int i = 30; i >= 0; --i){
        int one = cnt[r][i]-cnt[l-1][i];
        int zero = len-one;
        if (zero > one){
            ans |= (1<<i);
        }
    }
    return ans;
}
int main(void){
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        for (int j = 30; j >= 0; --j){
            if ((a[i]>>j)&1){
                cnt[i][j] = cnt[i-1][j]+1;
            }else{
                cnt[i][j] = cnt[i-1][j];
            }
        }
    }
    int q; cin >> q;
    while (q--){
        int l, r; cin >> l >> r;
        cout << solve(l, r) << endl;
    }
    return 0;
}