hdu 4737 A Bit Fun 2013成都赛区网络赛最后一题
题目会给出N(N<=100000)个数和一个m，定义f(i,j) 是第i个数到第j个数的或和 求出满足f(i,j)<m的(i,j) 有多少个（其中i<=j）？
做法有多种我用的是线段树 用2个标记在数组上进行挪动，一个表示区间的左端点一个表示区间的右端点，然后用线段树以logn的复杂度求出区间的或和，再进行统计。
具体代码如下：
/************************ hdu 4737 A Bit Fun*************************/#include<cstdio>#include<cstring>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=100005;int sum[maxn<<2],m,n,data[maxn];int cas=0;int build(int l,int r,int rt)//构建或和的线段树{if (l==r) return sum[rt]=data[l];int m=(l + r)>>1; return sum[rt]=build(lson)|build(rson);}int query(int L,int R,int l,int r,int rt) //L R 是要查询的区间，l r 是总区间 rt是根{ if (L<=l&&r<=R) return sum[rt]; int m=(l+r)>>1,ret=0; if(L<=m) ret|=query(L,R,lson); if(R>m) ret|=query(L,R,rson); return ret;}int read(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&data[i]); build(1,n,1); return 0;}void deal(){ int sta=1,en=1,ans=0,te,temp,f=0; while(sta<=n&&en<=n)//这里是枚举区间的左右端点的代码，可能写的比较麻烦 { temp=query(sta,en,1,n,1); if(en<n) { te=query(sta,en+1,1,n,1); if(temp<m&&te>=m) f=ans+=en-sta+1; else if(temp>=m) f=1; if(te<m) f=0; } if(temp<m&&en==n) f=ans+=en-sta+1; if(en==n&&temp>=m)f=1; if(sta==en&&en<n) f=0; f?sta++:en++; } printf("Case #%d: %d\n",++cas,ans);}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T;scanf("%d",&T); while(T--) { read(); deal(); } return 0;}