[关闭]
@Junlier 2018-09-16T16:12:24.000000Z 字数 1198 阅读 1958

莫队总结

算法——莫队
我学的时候 大米饼的莫队
既然学了这个神奇的东西,那我就来简单地总结一下

闲话要听

首先放一个例题: luogu 小B的询问
其实就是小z的袜子的弱化版。。。虽然网上都拿小z的袜子作模板讲,但是还得小小推个式子我当时学的时候就比较烦。。。
行吧,这两题的核心部分是一模一样的,你会发现小B的询问的答案就是小z的袜子的答案的分子。。。

无修改普通莫队

行吧我们入正题了
我现在说的莫队都只是无修改的莫队啊。。。
不需要觉得这个东西很难,虽然它并不简单。。。

前置


实现

  1. 对被操作序列分块(先理解为按分块吧)(先记下来,别问为什么!)
  2. 把所有的询问记录下来,按左端点排序,若左端点相同则按右端点排序
    注意,这里不是直接排序,我们把左端点是否相同定义为是否在同一个块内
    也就是说: 左端点按它所在块的编号排序,若两个左端点在同一个块内,则按右端点排序
  3. 枚举询问,做完了。。。(你暂时当我放屁)

解释一下为什么

不用多说,一切的一切都是为了保证复杂度,所以我们来推一下时间复杂度

  1. 首先最外层肯定得枚举个询问(已经排好序),我们用指针代表当前询问所在区间
  2. 看一下的移动复杂度:
    - 在同一个块内移动:每个询问最多
    - 不在同一个块内移动: 每个询问最多
    总的来说就是
  3. 然后是的移动复杂度:
    - 对于每一个块,r最多移动n次,我们又有个块
    那么复杂度是
  4. n和m的数量级一般差不多,所以整个莫队的复杂度就是滴辣

总结

怎么拓展上面也说了,怎么操作也就这样了,相信你依旧是懵的对不对,那我再总结一下

  1. 分块 对后面的作用可以往上再看一下
  2. 排序 对于所有询问我们做了排序,是为了保证我们的答案跟着询问拓展时的复杂度正确
  3. 地实现拓展 这个上面我应该讲的比较清楚了吧(当然每道题不同)

那么应该还是比较清晰了吧
几道题目练练手
luogu 小B的询问 https://www.luogu.org/problemnew/show/P2709
luogu 小Z的袜子 https://www.luogu.org/problemnew/show/P1494
luogu 异或序列 https://www.luogu.org/problemnew/show/P4462

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注