浅谈莫队

简介

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前,莫队算法已经在 Codeforces 的高手圈里小范围流传,但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时,只分析了普通莫队算法,但是经过 OIer 和 ACMer 的集体智慧改造,莫队有了多种扩展版本。

莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。

— OI wiki

普通莫队

引例:区间不同数

Description

有一个长度为 $n$ 的序列,有 $m$ 次询问,每次询问某个区间内出现过的数值种类数。

$1\leq n \leq 5\times 10^4,1\leq m \leq 2\times 10^5,0\leq a_i \leq 10^6$

Solution

首先考虑暴力,如果对于每一个询问,直接暴力枚举区间每个数,开个桶统计每个数字是否出现过,显然这种做法会超时,复杂度为 $O(NM)$。

这时候就要用到莫队算法了。

那么莫队是什么呢?

其实就是优雅的暴力

我们现在可以思考一个问题,如果你已经得知区间 $[l,r]$ 的答案,那么如何求区间 $[l,r+1]$ 的答案呢?

显然区间 $[l,r+1]$ 只比 $[l,r]$ 多了元素 $a[r]$,那么我们只需要判断 $a[r]$ 对答案是否有贡献即可。

那么什么时候 $a[r]$ 对答案有贡献呢?

显然只有当区间 $[l,r]$ 中 $a[r]$ 的出现次数为 $0$。

那么事情就很好办了,我们只需要开一个 $cnt$ 数组统计每个数字目前出现的次数,每次对答案造成贡献的条件是 $cnt[a[r]]==0$。

同理,我们如果知道了区间 $[l,r]$ 的答案,我们就可以知道 $[l-1,r],[l+1,r],[l,r-1]$ 的答案。

而且这个复杂度是 $O(1)$ 的,那么处理下一个询问的复杂度就是 $O(|r_i-r_{i-1}|+|l_i-l_{i-1}|)$ 的。

这样的复杂度在随机数据中表现很好,但是毒瘤的出题人也不难卡你。

那么此时就需要莫队优化的精髓来减小复杂度了。

我们考虑进行分块,不妨设块大小为 $\sqrt{N}$,把每个点分入一个块内,然后将所有询问按照左端点所在块为第一关键字排序,右端点的序号为第二关键字排序

下面我们来解释下为什么要这么做:

  1. 所在块相同时,右端点递增是 $O(N)$ 的,块共有个 $O(\sqrt{N})$,复杂度为 $O(N^{1.5})$
  2. 分块转移时,右端点最多变化 $N$,块共有 $O(\sqrt{N})$ 个,复杂度为 $O(N^{1.5})$
  3. 块相同时,左端点最多变化 $\sqrt{N}$,块转移时,左端点最多变化 $2\sqrt{N}$,共有 $N$ 个询问,复杂度为 $O(N^{1.5})$

所以总时间复杂度为 $O(N^{1.5})$。

Code

莫队的劣处

不难发现,莫队只支持离线区间询问,对于在线问题,我们并不能采用莫队来解决。

并且使用莫队需要一些卡常技巧,才能战胜出题人

带修莫队

一般的莫队是不支持修改的,但是如果我们稍微修改一下,就可以让莫队资瓷修改啦~

就像 DP 一样,可以强行加上一维时间维, 表示这次操作的时间。

时间维表示经历的修改次数。

即把询问 $[l,r]$ 变成 $[l,r,time]$。

那么我们的坐标也可以在时间维上移动,即 $[l,r,time]$ 多了一维可以移动的方向。

这样的转移也是 $O(1)$ 的,但是我们排序又多了一个关键字,再搞搞就行了。

可以用和普通莫队类似的方法排序转移,做到 $O(N^{\frac{5}{3}})$。

这一次我们排序的方式是以 $N^{\frac{2}{3}}$ 为一块,分成了 $N^{\frac{1}{3}}$ 块,第一关键字是左端点所在块,第二关键字是右端点所在块,第三关键字是时间。

还是来证明一下时间复杂度:

  • 左右端点所在块不变,时间在排序后单调向右移,这样的复杂度是 $O(N)$;
  • 若左右端点所在块改变,时间一次最多会移动 $N$ 个格子,时间复杂度 $O(N)$;
  • 左端点所在块一共有 $N^{\frac{1}{3}}$ 中,右端点也是 $N^{\frac{1}{3}}$ 种,一共 $N^{\frac{1}{3}}$ 种,每种乘上移动的复杂度 $O(N)$,总复杂度 $O(N^{\frac{5}{3}})$。

例题:LuoguP1903 [国家集训队]数颜色 / 维护队列

Description

有一个长度为 $n$ 的序列,要支持 $m$ 次询问或修改。

题目需要你进行的操作有:

  1. Q l r 表示询问 $[l,r]$ 中出现过的数值种类数。
  2. R p col 表示把第 $p$ 个数替换成颜色 $col$。

Solution

带修莫队模板

Code

树上莫队

直接类似于树分块,直接在 $Dfs$ 时,如果子树大小超过块大小就直接合成一个块即可。

其他操作类似于普通莫队。

显然,如果直接这样操作肯定是不行的。

因为两个端点还是需要计数的。

容易想到,只有 $LCA$ 才可能重复,所以每次不标记 $LCA$,询问答案时再标记,最后撤销即可。

例题:LuoguP4074 [WC2013] 糖果公园

Code

回滚莫队

例题:AT1219 歴史の研究

Solution

回滚莫队类似于普通莫队进行排序。

查询直接枚举每一个块,而该块所有右端点都是单调递增的,而左端点都在同一个块内移动,从而计算每个询问的值。

每次到下个块的左端点直接全部清空即可。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇