HDU 5694 BD String反復

BD String
テーマ接続:
http://acm.hdu.edu.cn/showproblem.php?pid=5694
Description
Problem Descriptionで知られていますが、ジグマの好きなキャラクターは二つしかありません.BとDです.
今日、BとDで文字列を構成する規則が発明されました.
S(1)=B
S(2)=BBD
S(3)=BBDBBDD
…
S(n)=S(n−1)+B+reverse(flip(S(n−1)
なお、reverse(s)は文字列を反転させることを指し、例えばreverse(BBD)＝DBB、flip(s)は文字列のBをDに置換し、Dはflip(BBD)＝DDBに置換する.
熊は普段はパソコンだけで遊んでいますが、これはこのマシンの比類のない演算速度を妨げていません.現在はS(21000)の内容を計算しましたが、度熊は熊だけなので、一度にこんなに長い文字列は読めません.この文字列のL番目(1からR番目)から、Bの数はどれぐらいですか?
Input
最初の行は整数Tで、T(1≦T≦1000)グループのデータを表します.
各グループのデータは、2つの数LとR(1≦L≦R≦1018)を含む.
Output
各グループのデータに対して、S(21000)で表される文字列のL番目からR番目のビットのBまでの個数が出力される.
Sample Input
3 1 3 1 7 8
Sample Output
2 4 3
ベント
題意
クイズ:
ソロを知ったら(i)、iを求める前にいくつのbがあるかを表します.
答えはソロ(r)-ソロ(l-1)ですか?
これはどうやって実現しますか?繰り返していけばいいです.
S[i]=s[i-1]+1+rs[i-1]
これは反復できます.複雑さはlognです.get関数のコードを具体的に見てください.
コード

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 61;
long long len[maxn],B[maxn],D[maxn],sumB[maxn];
void pre()
{
    len[1]=B[1]=sumB[1]=1;
    for(int i=2;i<maxn;i++){
        len[i]=2LL*len[i-1]+1;
        B[i]=D[i-1]+1+B[i-1];
        D[i]=B[i-1]+D[i-1];
    }
}
long long get(long long x)
{
    if(x==0)return 0;
    if(x==1)return 1;
    int p=lower_bound(len+1,len+61,x)-len;
    if(x==len[p])return B[p];
    if(x>=(len[p-1]+1)/2+1+len[p-1])
        return B[p-1]+1+get(x-len[p-1]-1)-1;
    return B[p-1]+1+get(x-len[p-1]-1);
}
void solve()
{
    long long l,r;
    scanf("%lld%lld",&l,&r);
    cout<<get(r)-get(l-1)<<endl;
}
int main()
{
    pre();
    int t;
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}