首页 > 代码库 > 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 ) 线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。