HDU4737线段树

本文主要是介绍HDU4737线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：给定一系列数，F(i,j)表示对从ai到aj连续求或运算，(i<=j)求F(i,j)<=m的总数。

const int Max_N = 100008 ;
int  sum[Max_N<<2] , x[Max_N] ;
int  n , m ;void  push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;
}void  update(int i , int a , int L , int R , int  t){if(L == R){ sum[t] |= a  ; return ; }int M = (L + R) >> 1 ;if(i <= M)  update(i , a , L , M , t<<1) ;else        update(i , a , M+1 , R , t<<1|1) ;push_up(t) ;
}int   query(int now , int  L , int R , int t){if((now|sum[t]) < m) return R ;if(L == R)  return -1 ;int M = (L + R) >> 1 ;if((now|sum[t<<1]) >= m)  return query(now , L , M , t<<1) ;else  return max(M , query(now|sum[t<<1] , M+1 ,R , t<<1|1)) ;
}int  main(){int i , t  , T  = 1  , r , ans ;cin>>t ;while(t--){scanf("%d%d" ,&n , &m) ;for(i = 1 ; i <= n ; i++)  scanf("%d" ,&x[i]) ;memset(sum , 0 , sizeof(sum)) ;ans = 0 ;for(i =  n ;  i >= 1 ; i--){update(i , x[i] , 1 , n , 1)  ;r = query(0 , 1 , n , 1) ;if(r != -1) ans += r - i + 1 ;}printf("Case #%d: %d\n" , T++ , ans) ;}return 0 ;
}

这篇关于HDU4737线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---