【牛客OI赛制测试赛3】 毒瘤xor

时间:2024-07-12 09:34:02

牛客OI赛制测试赛3 毒瘤xor

传送门

题面,水表者自重

Solution

前缀和简单题(挖坑待补)

代码实现

#include<stdio.h>
#define int long long
int a[100010],n,sum[100010][31],two[31],tmp[31];
void init(){
    two[0]=1;
    for(int i=1;i<31;i++)
        two[i]=two[i-1]<<1;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    init();
    for(int i=1;i<=n;i++){
        for(int j=0;j<31;j++)
            sum[i][j]=sum[i-1][j];
        for(int j=0;j<31;j++)
            if((a[i]>>j)&1)sum[i][j]++;
    }
    int q;scanf("%lld",&q);
    while(q--){
        int l,r;scanf("%lld%lld",&l,&r);int ans=0;
        for(int j=0;j<31;j++)
            tmp[j]=sum[r][j]-sum[l-1][j];
        for(int j=0;j<31;j++)
            if((r-l+1)>2*tmp[j])
                ans+=two[j];
        printf("%lld\n",ans);
    }
    return 0;
}