NEU1252 AND operation at intervals（线段树或二进制）

December 01, 2015

题目链接

题意：判断区间内的与和，OJ 中题目描述貌似有问题。

第一种方法：线段树搞即可，注意 longlong 和输出格式。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const long long maxn = 1e5+10;
long long value[maxn<<4+1];

void PushUp (long long rt){
    long long a = rt<<1;
    long long b = rt<<1|1;
    if(value[a] == -1)
        value[rt] = value[b];
    else if(value[b] == -1)
        value[rt] = value[a];
    else
    value[rt] = value[a] & value[b];
}

void build(long long l,long long r, long long rt){
    if(l == r){
        scanf("%lld", &value[rt]);
        return;
    }
    long long m = l + (r-l)/2;
    build(lson);
    build(rson);
    PushUp(rt);
}

long long query(long long L,long long R,long long l,long long r,long long rt){
    if(L <= l && R >= r)    return value[rt];
    long long m = l + (r-l)/2;
    long long ans = -1;
    if(L <= m){
        if(ans == -1){
            ans = query(L, R, lson);
        }else ans &= query(L, R, lson);
    }

    if(R > m){
        if(ans == -1){
            ans = query(L, R, rson);
        }else ans &= query(L, R, rson);
    }
    return ans;
}

int main(){
    long long n, m;
    while(scanf("%lld %lld", &n, &m) != EOF){
        memset(value, -1, sizeof(value));
        build(1, n, 1);
        for(int j = 1; j <= m; j++){
            long long a, b;
            scanf("%lld %lld", &a, &b);
            //flag = 1;
            printf("%lldn", query(a, b, 1, n, 1));
        }
        printf("n");
    }
    return 0;
}

第二种方法：&运算，二进制位都是 1，结果为 1，否则为 0。因此我们可以存储所有位的二进制前缀和。若前缀和做差正好等于区间长度，则这位是 1，否则是 0。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long a[100005];
int sum[100005][65]; //sum[i][j]表示前i个数在第j位的和
int main(){
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF){
      memset(sum, 0, sizeof(sum));
      for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        for(long long bit = 1, num = 1; bit <= 63; bit++, num <<= 1){
            sum[i][bit] = sum[i-1][bit] + ((a[i]&num)>0);
        }
      }
      while(m--){
        int l, r;
        scanf("%d %d", &l, &r);
        long long ans = 0;
        for(long long i = 1, num = 1; i <= 63; i++, num <<= 1){
            if(sum[r][i] - sum[l-1][i] == r-l+1){
                ans += num;
            }
        }
        printf("%lldn", ans);
      }
      cout << endl;
    }
    return 0;
}

交第二种方法时又被格式坑了。。。