前言
byd 最近的人天天都在学这个 我也来看一看
0 概念
什么是莫队
可以先去看看分块 这样就很好理解
先丢出一个问题：
- 给出 \(m\) 个区间 \(l,r\) 求区间众数
这就是蒲公英 在线用分块可以做到 \(O(n\sqrt n)\) 的复杂度
现在我们思考一下
线段树可以做什么？满足区间合并的问题
树状数组可以做什么？满足区间相减的问题
如果这两都做不了？
这下我们的乱搞神器莫队就出来了
它有 \(O(n\sqrt n)\) 的优秀时间复杂度
1 普通莫队
有很多问题 每个重复求很麻烦 不妨按照一个顺序来做
第一步思考：按 \(l\) 左端点排序 时间复杂度 \(O(n^2)\)
太慢了！
莫队思路：首先，按 \(l\) 左端点所处在的块排序 同一块内的按右端点排
这样，块长为 \(S=\sqrt n\) 总共有\(\frac{n}{S}\) 块
每个询问左端点时间复杂度遍历是 \(O(S)\) 的 右端点是 \(O(n)\)的均摊时间复杂度
时间复杂度 \(O(n\sqrt n)\)
好！