莫队

莫队算法

0x00 简介

• 什么是莫队算法？
• 现在假设我们有一个序列，需要实现一些询问操作
• 但这个询问操作非常麻烦，既不能做区间加法也不能做区间减法，一个一个的添加或者删除倒是可行的（可以在$ O(1)$ 或 $ log_{n} $时间内完成），而且询问是离线的
• 我们不能暴力枚举所有询问，这样复杂度是接近$ O(nq) $的
• 但是用一种合理的顺序安排询问，我们可以使询问区间的端点移动次数变为(qsqrt(n))这个级别，甚至可以卡过一些两个log或者一个大log的题

0x01 具体思路

• 那么我们如何构造这一精妙的顺序呢？
• 我们把整个序列分成 $ sqrt{n} $ 块，每块大小就是 $ sqrt{n} $ ，然后将询问重新排序，第一关键字为左端点所在块的序号，第二关键字为右端点的坐标
• 我们发现，对于同一个块内的询问，左端点位移一次不超过 (sqrt{n})，右端点单调增，这样对于一个块内的询问，左端点移动不超过 $ tsqrt{n} $ （t是这个块内的询问个数），右端点移动不超过n次，对于所有询问，左右端点的移动次数之和超过 $ (n+q)sqrt{n}$，而每一次移动是 $ O(1) $ 或 $ log_{n}$ 的，所以就搞完了！
• 具体实现可以看我的代码

带修改的莫队算法

0x00 搞法

• 顾名思义嘛，就是有修改的莫队
• 这怎么搞？
• 对于每个询问，记录这个询问之前的最后一次修改的编号
• 和莫队一样对询问排序，然后暴力处理修改对询问的影响
• 但这次分的块的大小是 $ n^{frac{2}{3}}$，具体为什么，证明我也不会。。反正是对的
• 对于一些具体的问题你可能需要微调块的大小
• 具体实现可以看我的代码

树上的莫队算法

0x00 搞法

• 这个名字看上去有歧义啊
• 简而言之就是询问树上的一条链
• 做法是按照dfs序分块排序，移动询问的时候，比如我们要从(u,v)移动到(x,y)，我们将<u,LCA(u,x)>，<x,LCA(u,x)>这两条路径上的点存在性取反，对v和y也一样搞
• 注意LCA只要取反一次，画个图理解一下
• 正确性很显然对吧，还省略了烦琐的讨论，VFK%%%%%%
• 具体实现可以看我的代码
• 4.10更新：vfk害我！骗我王室联邦分块，直接按照dfs序分块就行！终于搞完了糖果公园
• 更新：我王室联邦写错了！！！！