观察一下,将整个过程写出来,会发现形成一棵满二叉树,每一层要么全是0,要么全是1。

输出的顺序是其中序遍历。

每一层的序号形成等差数列,就计算一下就可以出来每一层覆盖到的区间的左右端点。

复杂度O(log(n))。

#include<cstdio>
using namespace std;
typedef long long ll;
ll n,l,r;
bool a[66];
int e;
int main()
{
// freopen("b.in","r",stdin);
scanf("%I64d%I64d%I64d",&n,&l,&r);
if(n==0)
{
puts("0");
return 0;
}
while(n)
{
a[++e]=n%2ll;
n/=2ll;
}
ll j=1;
int ans=0;
for(int i=e;i;--i)
{
if(a[i])
{
ll L=(l-j)/(j*2)+((l-j)%(j*2)!=0);
if(l<j) L=0ll;
ll R=(r-j)/(j*2);
if(r<j) R=-1ll;
ans+=(int)(R-L+1ll);
}
j*=2ll;
}
printf("%d\n",ans);
return 0;
}

最新文章

  1. Python语言特性之3:@staticmethod和@classmethod
  2. iOS,Xcod7/8,iOS使用修改点
  3. ThinkPHP3.2.3自带的分页用法--很简单实用
  4. python的变量
  5. codevs 1203 判断浮点数是否相等
  6. MySQL版本调研
  7. swift(一)
  8. kmalloc/kfree,vmalloc/vfree函数用法和区别
  9. 过滤所有的HTML标签
  10. javascript回调函数
  11. trailingZeroes
  12. Objective-C内存管理教程和原理剖析(四)
  13. ionic3 app 退出应用程序
  14. windows 下安装MySQL 服务无法启动类问题
  15. HDU4651 Partition 【多项式求逆】
  16. 【LOJ#6072】苹果树(矩阵树定理,折半搜索,容斥)
  17. python之装饰器(decorator)
  18. Oracle中使用PL/SQL如何定义参数、参数赋值、输出参数和 if 判断
  19. Lucene 学习-安装 Kibana 视图界面
  20. robot framework添加库注意事项

热门文章

  1. 解决mysql的日志文件过大的问题
  2. ZooKeeper Watcher注意事项
  3. 转:安装成功的nginx如何添加未编译安装模块
  4. Nginx的client_header_buffer_size和large_client_header_buffers学习
  5. All in One到”分布式“迁移过程中的坑
  6. 微信小程序登录状态
  7. 关于jQuery.extend
  8. Linux curl命令【curl】
  9. popen &amp;&amp; pclose函数
  10. sql文格式替换