莫队,一个很好玩的算法,基础莫队可以以 \(O(m\sqrt{n})\) 轻松处理 RMQ 一类的问题。狠狠恶心一下不爱开大数据的出题人
从基础开始。
普通莫队
对于 RMQ 问题,我们一般采取 ST 表、线段树等 log 级别的数据结构维护,但有些题目很难用这些数据结构维护,此时可以尝试莫队。
介绍
首先,莫队的底层逻辑是由 \([l,r]\) 区间的答案来更新 \([l-1,r]\),\([l+1,r]\),\([l,r-1]\),\([l,r+1]\) 的答案。大多数情况下,这个转移是 \(O(1)\) 的,不过有的题也会改。
莫队就是让一对 \([l,r]\) 不断的在 \([1,n]\) 上移动,以此记录每个查询的结果。
如果我们在线实现这一操作,容易发现可能被卡到 \(O(nm)\) 的复杂度,莫队就是要让查询离线,找一个顺序让区间移动的次数尽量少,做到 \(O(m \sqrt{n})\) 复杂度。
优化方法
容易发现,可以尽量让 \(l\) 不动,让 \(r\) 不断在区间上移动查询。于是我们就可以对查询以 \(l\) 为第一关键字排序,以 \(r\) 为第二关键字排序。
但是随便模拟一下就会发现这玩意也太好卡了吧,我只需要让每个 \(l\) 都不同,然后让 \(r\) 的差距特别大不就行了?
于是,就涉及到另一个毒瘤数据结构了————分块,没学过的朋友们可以去稍微看一下,基础不难。
对于这 \([1,n]\) 的序列,将它分成 \(\sqrt{n}\) 个块,所以每个块的长度也是 \(\sqrt{n}\) 级别的。
然后,我们以 \(l\) 所在的块为第一关键字,以 \(r\) 为第二关键字排序,容易发现,一个块中包含了 \(l\) 的所有查询,\(l\) 移动的量级为 \(\sqrt{n}\),\(r\) 最多移动 \(n\) 次。
奇偶性优化
对于每个块,如果它的编号为奇数,那么让其中的查询以 \(r\) 升序排序,为偶数则以 \(r\) 降序排序。它可以让查询的 \(l\) 在不同块时,\(r\) 移动的长度尽量小。在查询比较密集时优化效果比较明显。