下山

今天是小X跟随师父学习编程的最后一天，这天早晨师傅给了他一个列表，列表中已有一个数n(0 <= n < 2^50)。

师傅告诉小X：“从现在开始，对于列表里的每个大于1的数x，你要先删掉它，然后用 x/2 , x%2 , x/2 三个数插入他原本的位置，直到没有数大于1，

傍晚时我会给你一个区间 [ l , r ]，你要告诉我列表内下标位于此区间内的1的个数”( l >= 1 , r >= 1 )

小X想出色的完成任务让师傅放心，他已经写了大部分代码了，你能帮他完成剩下的两个空吗。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll l,r;
ll length(ll n)
{
if(n<=1) return 1;
return 2*length(n/2)+1;
}
ll cal(ll n,ll l,ll r)
{
if(l>r||l<=0||r<=0||n<mark>0)
return 0;
if(n</mark>1)
return 1;
ll len=length(n);
ll mid=len/2+1;
if(r<mid)
return cal(n/2,l,r);
else if(l>mid)
return _______________;
else
return _______________;
}
int main() {
scanf("%lld%lld%lld",&n,&l,&r);
printf("%lld\n",cal(n,l,r));
return 0;
}

解题报告：我认为做对这道题的关键要素要理解递归的三个参数的意思，n代表当前这一层的值，l,r代表当前这一层的查询区间。要是询问的区间在他总子树的左边就往左边递归，要是在右边就往右边递归，要是左端点在左边，右端点在右边那就两边都加同时别忘记加中间的节点。附上一张本人的丑图。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll l,r;
ll length(ll n)
{
   
    if(n<=1) return 1;
    return 2*length(n/2)+1;
}
ll cal(ll n,ll l,ll r)
{
   
    if(l>r||l<=0||r<=0||n==0)
    return 0;
    if(n==1)
    return 1;
    ll len=length(n);
    ll mid=len/2+1;
    if(r<mid)
        return cal(n/2,l,r);
    else if(l>mid)
        return cal(n/2,l-mid,r-mid);
    else
        return cal(n/2,l,mid-1)+n%2+cal(n/2,1,r-mid);
}
int main() {
   
    scanf("%lld%lld%lld",&n,&l,&r);
    printf("%lld\n",cal(n,l,r));
    return 0;
}