注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

莫队+分块(未完待续)  

2014-06-10 22:31:59|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
搞懂了莫队原理。首先莫队一般用来求离线无修改区间值等,而且比如l,r到l+1,r的转移要O(1)的,或者O(log N)也可以。这样效率非常可观。我们只需要先把N分别sqrt(N)快,然后对于同一个块里的l,我们把它们按照r递增或者递减,保证相邻快是不同的顺序。这样我们可以发现:暴力完成了某个L,R,假设下一个l,r满足l<L,r>R.然后我们将R调到了r,由于是递增的,R最多调到N,即做N次,在同一个快中。这样再下一个快里,由于是递减的,所以我们直接从R较大的往小的减了,这样效率又保证了是N次的。

然后我们总结一下:对于每个块中的R,最多做M个,有sqrt(N)快,所以R移动的步数最多是O(M*sqrt(N));
对于每个L,由于在不同一块中是有序的,所以最多移动sqrt(N)次,有M个L,那么效率是
O(M*(sqrt(N)));
假使M=N,为了方便。
总的结合效率便是O(Nsqrt(N));在某些题中甚至比O(N(log(N))^2)跑得快。

对于分块大法:一般用于求涉及区间类问题,比如你原本要开数组记F[I][J]的某些东西,但发现N有10000这么大,这是你可以把N分块,F[I][J]表示第i块到第j块之间的东西。那么询问的话同块内暴力,块外直接加F[I+1][J-1]+暴力;
  评论这张
 
阅读(13683)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018