题解 | #毒瘤xor#

前缀和和位运算的基本运用。另外还有贪心的思想。

关于位运算上的数什么时候取1，这取决于当前区间上的数中该位置是1多还是0多。

因为多组解要求最小的，所以只有当1的个数严格<总个数的一半的时候，X的这一位才取1。

没有必要给中间值开double，直接让前面乘以2即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int cnt[100007][40];
void turn(int n,int x)
{
    int m = 0;
    for (int i = 0; i <= 30; i++)cnt[n][i] += cnt[n - 1][i];//前缀和处理
    while (x)
    {
        if (x & 1)cnt[n][m]++;
        x >>= 1;
        m++;
    }
}
long long quick(int x,int n)//快速幂
{
    long long tmp = x, ans = 1;
    while (n)
    {
        if (n & 1)ans = ans * tmp;
        n >>= 1;
        tmp *= tmp;
    }
    return ans;
}
long long deal(int l,int r)
{
    long long ans = 0;
    int n = r - l + 1;//区间长度。注意这里的n不是总长度。本人被卡这里
    for (int i=0;i<=30;i++)
    {
        if ((cnt[r][i] - cnt[l - 1][i])*2<n)//数量比较
        {
            ans += quick(2,i);
        }
    }
    return ans;
}
int main()
{
    int n;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        int x; scanf("%d",&x);
        turn(i,x);
    }
    int q; cin >> q;
    int l, r;
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d",&l,&r);
        printf("%lld\n",deal(l,r));
    }
    return 0;
}