首页 > 代码库 > Hdu4737 ( A Bit Fun ) 线段树

Hdu4737 ( A Bit Fun ) 线段树

题意:统计最后有多少对[i,j]使得其区间内所有的值的或的值<m

 

| 是非递减运算,线段树维护区间和 然后顺序统计下。

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include <math.h>using namespace std;typedef long long LL;const LL maxn = 111111;LL sum[maxn<<2];#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1void up(LL rt){    sum[rt] = sum[rt << 1] | sum[rt << 1 | 1];}void build(LL l, LL r, LL rt){    if (l == r){        scanf("%I64d", &sum[rt]); return;    }    LL mid = (l + r) >> 1;    build(lson);    build(rson);    up(rt);}LL ask(LL L, LL R, LL l, LL r, LL rt){    if (L <= l&&r <= R) return sum[rt];    LL mid = (l + r) >> 1;    LL ans = 0;    if (L <= mid) ans |= ask(L, R, lson);    if (R > mid) ans |= ask(L, R, rson);    return ans;}int main(){    LL t, n, m;    cin >> t;    for (LL i = 1; i <= t; i++){        scanf("%I64d%I64d", &n, &m);        build(1, n, 1);        LL pos = 1;        LL ans = 0;        for (LL j = 1; j <= n; j++){            while (pos <= j&&ask(pos, j, 1, n, 1) >= m) pos++;            if (pos <= j) ans += (j - pos + 1);        }        printf("Case #%I64d: %I64d\n",i,ans);    }    return 0;}

 

Hdu4737 ( A Bit Fun ) 线段树