学步园

这题和上次做的Uva11361和相似，也是区间查询，利用前缀数组来存，结果为a[r]-a[l-1]。

这题注意转化为求每一位的1的个数和。

做题时遇到一个小的问题，(0<<1)=0，调试了好久，以后得注意了。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll __int64
using namespace std;
void fun(int x,ll *a)
{
    if(x<=0)
    {
        return ;
    }
    int d=0,tx=x;
    while(tx)
    {
        tx/=2;
        d++;
    }
    for(int i=d; i>=1; i--)
    {
        if(i==1)
        {
            if(x&1)
                a[i]+=1;
            continue;
        }
        if(x&((int)(pow(2.0,i-1))))
        {
            a[i]+=(1+x%((int)pow(2.0,i-1)));
            for(int j=i-1; j>=1; j--)
            {
                a[j]+=pow(2,i-2);
            }
            x-=(int)pow(2.0,i-1);
        }
    }
}

int main()
{
    int l,r;
    ll x[66];
    ll y[66];
    while(scanf("%d%d",&l,&r)!=EOF)
    {
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        fun(l-1,x);
        fun(r,y);
        ll sum=0,tmp=0,a;
        for(int i=1; i<64; i++)
        {
            a=y[i]-x[i];
            tmp=(tmp+a)/2;
            sum+=tmp;
        }
        printf("%I64d\n",sum);
    }
    return 0;
}