莫队，一个很好玩的算法，基础莫队可以以 \(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\) 移动的长度尽量小。在查询比较密集时优化效果比较明显。