【每日一题】 毒瘤xor

数学+前缀和。

对于序列中的每一个数，采用二进制表示，以此判断X在每一位的值。

先考虑区间[1,n]，假设这n个数有t个数的第j位为1，则有(n-t)个数的为0。接下来判断X在第j位应该是0还是1。
已知异或的运算规则：相同为0，不同为1。如果要使求和得到的值尽可能大，那么X与每一个数的第j位异或运算后得到的1应该尽可能多。所以比较t与n-t的大小关系即可，若t>n-t，则1较多，X的第j位应该为0；反之则为1。有一点需要注意，题目要求在求和值尽可能大的同时，X的值要尽可能小，所以当0与1一样多时，X的第j位应为0。其它位以此规则可算出，最后累加即可。

当考虑区间[l,r]时，采用同样思路，不过由于询问次数过多，采用前缀和处理每一位为1的个数。

代码：

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
#define fir first
#define sec second
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=1e9+7;
const int maxn=1e5+9;
const ll maxx=1e12+9;

int n,q,l,r,ar[maxn];
int sum[maxn][33];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&ar[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<31;j++)
            sum[i][j]=sum[i-1][j]+((ar[i]>>j)&1);
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&l,&r);
        int ans=0;
        for(int j=0;j<31;j++)
            if(sum[r][j]-sum[l-1][j]<(r-l+2)/2) ans+=(1<<j);
        printf("%d\n",ans);
    }
}