CodeForces 768 B.Code For 1（递归）

Description

初始序列只有 n n $n$一个元素，每次操作会把序列中每个大于1$1$$1$的元素 x x $x$变成⌊x2⌋,x%2,⌊x2⌋$\lfloor \frac{x}{2}\rfloor ,x\mathrm{\%}2,\lfloor \frac{x}{2}\rfloor$$\lfloor\frac{x}{2}\rfloor,x\%2,\lfloor\frac{x}{2}\rfloor$，直至序列所有数字变成 0 0 $0$或1$1$$1$为止，问操作结束后序列第 l l $l$个元素到第r$r$$r$个元素之间有多少 1 1 $1$

Input

三个整数n,l,r$n,l,r$$n,l,r$，保证 r r $r$不超过序列长度(0≤n<250,0≤r−l≤105,r,l≥1)$(0\le n<2^{50},0\le r-l\le {10}^5,r,l\ge 1)$$(0\le n<2^{50},0\le r-l\le 10^5,r,l\ge 1)$

Output

输出操作结束后序列第 l l $l$个元素到第r$r$$r$个元素之间有多少 1 1 $1$

Sample Input

7 2 5

Sample Output

4

Solution

对于一个元素x$x$$x$，假设 2n≤x<2n+1 2 n ≤ x < 2 n + 1 $2^n\le x<2^{n+1}$，那么需要 n n $n$次操作才能把x$x$$x$变成若干 0 0 $0$和1$1$$1$，简单计算得 x x $x$会变成一个长度为2n+1−1$2^{n+1}-1$$2^{n+1}-1$的 01 01 $01$序列，且其中共 x x $x$个1$1$$1$（数学归纳法即可），进而可以递归解决该问题，假设当前在统计 x x $x$所形成的区间[L,R]$[L,R]$$[L,R]$的贡献（答案即求 n n $n$所形成的整个区间的贡献），如果该区间被查询区间包含则贡献即为x$x$$x$，如果该区间与查询区间不相交则贡献为 0 0 $0$，否则把该区间按操作要求分成左中右三块，令mid$mid$$mid$为区间中点，则左半部分为由 ⌊x2⌋ ⌊ x 2 ⌋ $\lfloor\frac{x}{2}\rfloor$形成的区间 [L,mid−1] [ L , m i d − 1 ] $[L,mid-1]$的贡献，右半部分为由 ⌊x2⌋ ⌊ x 2 ⌋ $\lfloor\frac{x}{2}\rfloor$形成的区间 [mid+1,R] [ m i d + 1 , R ] $[mid+1,R]$的贡献，中间为 x%2 x % 2 $x\%2$对答案的贡献，递归求解即可

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
ll deal(ll n)
{
    ll t=log2(n);
    return (1ll<<(t+1))-1;
}
ll Solve(ll n,ll L,ll R,ll l,ll r)
{
    if(n==0)return 0;
    if(l<=L&&R<=r)return n;
    if(r<L||l>R)return 0;
    ll mid=(L+R)/2;
    return Solve(n/2,L,mid-1,l,r)+Solve(n%2,mid,mid,l,r)+Solve(n/2,mid+1,R,l,r);
}
int main()
{
    ll n,l,r;
    while(~scanf("%I64d%I64d%I64d",&n,&l,&r))
        printf("%I64d\n",Solve(n,1,deal(n),l,r));
    return 0;
}