思路:
L[i],R[i]分别表示node==i时这个串的左右端点,dp[i][0]表示node==i时B的个数,dp[i][1]表示D的个数;
给一个区间[l,r]进行分治,mid=(L[i]+R[i])/2,如果rmid时这时就可以把求node==i-1时的[l,r]的B的
个数转化成求node==i-1时的[l',r']的D的个数,在转化成求r'-l'-[l',r']里面的B的个数,递归就可以了,
当l
AC代码:
#include
/*
#include
#include
#include
#include
#include
#include
#include
*/
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i
#define Rjep(n) for(int j=1;j
#define Rjop(n) for(int j=0;j
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int N=1e5+25;
int n;
LL L[70],R[70],dp[70][2];
int fun()
{
L[1]=1;
R[1]=1;
dp[1][0]=1;
dp[1][1]=0;
for(int i=2;i
{
L[i]=1;
R[i]=2*R[i-1]+1;
dp[i][0]=dp[i-1][0]+1+dp[i-1][1];
dp[i][1]=dp[i-1][0]+dp[i-1][1];
}
}
LL dfs(LL l, LL r,int node)
{
if(l>r||node
if(l==L[node]&&r==R[node])return dp[node][0];
LL mid=(L[node]+R[node])>>1;
if(r<=mid)
{
if(r==mid)return 1+dfs(l,r-1,node-1);
else return dfs(l,r,node-1);
}
else
{
if(l>=mid)
{
if(l==mid)return r-l+1-dfs(R[node]-r+1,R[node]-l,node-1);
else return r-l+1-dfs(R[node]-r+1,R[node]-l+1,node-1);
}
else return dfs(l,mid-1,node-1)+1+r-mid-dfs(R[node]-r+1,R[node]-mid,node-1);
}
}
int main()
{
int t;
scanf("%d",&t);
fun();
while(t--)
{
LL l,r;
scanf("%I64d%I64d",&l,&r);
LL ans=dfs(l,r,62);
printf("%I64d\n",ans);
}
return 0;
}