莫队理解笔记

背景:这就是莫队算法。为什么叫莫队算法呢?据说这是2010年国家集训队的莫涛(3)在作业里提到了这个方法。

由于莫涛经常打比赛做队长,大家都叫他莫队,该算法也被称为莫队算法...(摘自:aaa.com)

主要用来写一些比较优秀的暴力。。。当然要慎用万一比n^2慢了呢...

细节:  先排序!先排序!先排序!!!

   复杂度要注意!要注意!要注意!别比n^2慢了啊,对拍一下调一调块大小什么的或者干脆写n^2...

   伸缩时的复杂度比较关键,一般为O(1).

    时间范围较宽松且能离线时考虑使用。

网上好话:”摘自这里:aaa.com"

  1.如果数据较小,用数组,时间复杂度为O(1);如果数据较大,可以考虑用离散化或map,时间复杂度为O(logn)。

  2.举个例子,有6个询问如下:(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。

  这个数据已经按照左端点排序了。用上述方法处理时,左端点会移动6次,右端点会移动移动98+97+95+98+95=483次。右端点大幅度地来回移动,严重影响了时间复杂度——排序的复杂度是O(mlogm),所有左端点移动次数仅为为O(n),但右端点每个询问移动O(n),共有m个询问,故总移动次数为O(nm),移动总数为O(mlogm + nm)。运行时间上界并没有减少。

  其实我们稍微改变一下询问处理的顺序就能做得更好:(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。

  左端点移动次数为2+2+1+2+2=9次,比原来稍多。右端点移动次数为2+3+95+3+1=104,右端点的移动次数大大降低了。  

操作:以分块为基础(说的不对谅解),分成几个块维护并查询(通过伸缩),通过排序使我们的左右端点移动变少。

原文地址:https://www.cnblogs.com/three-D/p/11240658.html