CF 768B

CF 768B题意：In each operation Sam must remove any element x, such that x>1, from the list and insert at the same position x/2,x%2,x/2 sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.给定一个数N，对大于1的数在原来的位置拆分为N/2，N%2，N/2三个数。对拆分出的大于1的数同样进行拆分，直至所有的数均为0或1。Now the masters want the total number of 1s in the range l to r (1-indexed). 对拆分后的0/1序列，询问L到R区间中1的数量类似于线段树的区间查询思路1：简单题，递归思想。对于给定的N，可以计算出最终0/1序列的长度。递归模拟，一层层往下分解，将得到的数分解到序列的对应指定位置中，当无法分解时则返回值，最后递归得到区间内所有的1的个数      这里我担心被卡，用了一个位运算小优化。其实不用也可以。Code：#include<cstdio>typedef long long ll;ll n,ql,qr,len=1,ans;ll dfs(ll n,ll l,ll r){    if(n==0||l>qr||r<ql) return 0;    if(n==1) return 1;    ll mid=l+r>>1;    return dfs(n>>1,l,mid-1)+dfs(n&1,mid,mid)+dfs(n>>1,mid+1,r);}int main(){    scanf("%I64d%I64d%I64d",&n,&ql,&qr);    for(ll x=n;x>1;x>>=1,len=len<<1|1);    ans=dfs(n,1,len);    printf("%I64d\n",ans);    return 0;}思路2：求出区间端点的前缀和相减，拆分的个数符合f(n)=2*f(n-1)+1，而n拆后的区间和一定是n，所以用二分找出端点位置即可