BD String
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 582 Accepted Submission(s): 256
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替换为B，比如flip(BBD)=DDB。
虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，目前它已经算出了S(21000)的内容，但度度熊毕竟只是只熊，一次读不完这么长的字符串。它现在想知道，这个字符串的第L位（从1开始）到第R位，含有的B的个数是多少？
今天，它发明了一种用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替换为B，比如flip(BBD)=DDB。
虽然度度熊平常只用它的电脑玩连连看，这丝毫不妨碍这台机器无与伦比的运算速度，目前它已经算出了S(21000)的内容，但度度熊毕竟只是只熊，一次读不完这么长的字符串。它现在想知道，这个字符串的第L位（从1开始）到第R位，含有的B的个数是多少？
Input
第一行一个整数T，表示T(1≤T≤1000) 组数据。
每组数据包含两个数L和R(1≤L≤R≤10^18) 。
每组数据包含两个数L和R(1≤L≤R≤10^18) 。
Output
对于每组数据，输出S(2^1000)表示的字符串的第L位到第R位中B的个数。
Sample Input
3
1 3
1 7
4 8
Sample Output
2
4
3
Source
解题思路：首选预处理出来每个字串的长度和其中B的个数。首先假设要找从1->x之间有少B，我们找到最长的且小于等于x的字串，然后判断是否等于，如果等于返回结果。否则以B为分隔的后边该字串翻转替换字串中B的个数可以通过前面的字串转化求解。如BBDBBDD B BBDDBDD。以中间的“B”作为分隔将串分成：前、分隔B、后，如果要求的是x是13，那么后边的部分（位置13粗体B）的B的个数= 前面黑体的长度 - （前面部分B的个数-前面非黑体部分B的个数）。前面非黑体部分B的个数就是递归求解即可。
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<string>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
#define mid (L+R)/2
#define lson rt*2,L,mid
#define rson rt*2+1,mid+1,R
#pragma comment(linker, "/STACK:102400000,102400000")
const int maxn = 1e5+300;
const LL INF = 1000000000000;
typedef long long LL;
typedef unsigned long long ULL;
LL len[100], f[100], ff[100];
LL cal(LL x){
if(x <= 0) return 0;
LL ret = 0, num;
int i;
for(i = 1; i <= 63; i++){
if(len[i] <= x){
ret = f[i];
}else{
break;
}
}
i--;
if(len[i] == x){
return ret;
}else{
return ret + 1 + (x-len[i]-1) - ( ret - cal(2*len[i]-x+1) );
}
}
int main(){
// freopen("Input.txt","r",stdin);
// freopen("Out.txt","w",stdout);
f[1] = 1;
len[1] = 1;
for(int i = 2; i <= 64; i++){ //64
f[i] = len[i-1] + 1;
len[i] = len[i-1]*2 + 1;
ff[i] = len[i] - f[i];
}
int T;
scanf("%d",&T);
while(T--){
LL l, r;
scanf("%lld%lld",&l,&r);
LL ln, rn;
ln = cal(l-1); rn = cal(r);
printf("%lld
",rn - ln);
}
return 0;
}