hdu4737A Bit Fun 線段樹

hdu4737A Bit Fun 線段樹

//給一串序列，問有多少對[i,j]使得
//[i,j]區間的所有數的或的值小於m
//可以知道'或'操作的加(a|b)>=max(a,b)
//可以枚舉區間的右邊r，找左邊第一個不滿足的位置
//然後在它們中間的r為由邊界的區間都沒滿足
//對於找第一個不滿足的位置，可以用線段樹做，
#include
#include
#include
using namespace std ;
const int maxn = 100010 ;
#define left v << 1
#define right v<<1|1
struct node
{
    int l , r ;
    int value ;
}tree[maxn<<2] ;
int h[maxn] ;
int m ,n;
void build(int l , int r , int v)
{
    tree[v].l = l ;
    tree[v].r = r ;
    if(l == r)
    {
        tree[v].value = h[l] ;
        return  ;
    }
    int mid = (l + r) >> 1 ;
    build(l , mid , left) ;
    build(mid + 1 , r , right) ;
    tree[v].value = tree[left].value|tree[right].value ;
}
int get_ans(int v , int sum)
{
    if(tree[v].l == tree[v].r)
    return tree[v].l ;
    int mid = (tree[v].l + tree[v].r) >> 1 ;
    if((sum|tree[right].value) >= m)
    return get_ans(right , sum) ;
    else return get_ans(left , sum|tree[right].value) ;
}
int ans = 0 ;
int query(int v , int pos)
{
    if(tree[v].l == tree[v].r)
    return tree[v].value ;
    int mid = (tree[v].l + tree[v].r) >> 1 ;
    int sum ;
    if(pos <= mid)
    query(left , pos) ;
    else
    {
        sum = query(right , pos) ;
        if(sum < m && (sum|tree[left].value) >= m)
        {ans = get_ans(left , sum) ;}
        return sum|tree[left].value;
    }
}
int main()
{
    //freopen(in.txt ,r ,stdin) ;
    int T ;
    scanf(%d ,&T) ;
    int cas = 0 ;
    while(T--)
    {
        scanf(%d%d ,&n , &m) ;
        for(int i = 1;i <= n;i++)
        scanf(%d ,&h[i]) ;
        build(1 , n , 1) ;
        int sum = 0;
        for(int i = 1;i <= n ;i++)
        {
            ans = 0 ;
            if(h[i] >= m)
            {continue;}
            query(1 , i) ;
            sum += (i - ans);
        }
        query(1 , 9) ;
        printf(Case #%d:  ,++cas) ;
        printf(%d
 ,sum) ;
    }
}