1 #include <bits/stdc++.h> 2 using namespace std; 3 long long bit[70]; 4 void init() 5 { 6 ????bit[1]=1; 7 ????for(int i=2;i<=55;++i) 8 ????{ 9 ????????bit[i]=2*bit[i-1]+1;10 ????}11 }12 long long getRes(long long n,long long ?x)13 {//数字n,第x位14 ????if(x==0)return 0;15 ????long long res=0;16 ????long long bitsCnt=bit[lower_bound(bit+1,bit+55+1,n/2)-bit];17 ????//printf("n=%I64d,x=%I64d,bitsCnt=%I64d\n",n,x,bitsCnt);18 ????if(n==1)return 1;19 ????if(x==bitsCnt+1)20 ????{21 ????????if(n%2==1)res++;22 ????????res+=n/2;23 ????????return res;24 ????}25 ????else if(x>bitsCnt+1)26 ????{27 ????????if(n%2==1)res++;28 ????????res+=n/2;29 ????????res+=getRes(n/2,x-bitsCnt-1);30 ????}31 ????else 32 ????{33 ????????res+=getRes(n/2,x);34 ????}35 ????//printf("res=%I64d\n",res);36 ????return res;37 }38 int main() {39 ????long long n,l,r;40 ????init();41 ????scanf("%I64d%I64d%I64d",&n,&l,&r);42 ????if(n==0)43 ????{44 ????????printf("0\n");45 ????????return 0;46 ????}47 ????int index=lower_bound(bit+1,bit+55+1,n)-bit;48 ????long long res1=getRes(n,l-1);49 ????long long res2=getRes(n,r);50 ????//printf("res1=%I64d,res2=%I64d\n",res1,res2);51 ????printf("%I64d\n",res2-res1);52 ????return 0;53 }题目：
Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x?>?1, from the list and insert at the same position , , sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.
Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?
The first line contains three integers n, l, r (0?≤?n?<?250, 0?≤?r?-?l?≤?105, r?≥?1, l?≥?1) – initial element and the range lto r.
It is guaranteed that r is not greater than the length of the final list.
Output the total number of 1s in the range l to r in the final sequence.
分析：
非常有趣的一道题，就是说我们有一个数n我们把它打散为一串0，1序列，方式如上所述，问l到r中有多少个1。
打散方式：比如说7，。
先通过找规律我们可以发现以下两条结论:
1，数x打散后的序列中有x个1。
2，数x打散后的序列有 2n-1位数，其中2n-1为刚好大于等于x的数。
现在给你l,r，问从第l位到第r位有多少个1.
那么这个问题，我们就可以转化为第x位以前有多少个1，然后再相减，就是答案了。
我们可以采用线段树的思想，
这样我们就可以利用第2条确定向左走还是向右走，第1条来确定有多少个1了。
http://codeforces.com/problemset/problem/768/B ?B. Code For 1
原文地址：http://www.cnblogs.com/sun-yinkai/p/7826108.html