莫队

分手后的思念是犯贱 2021-12-17 07:49 236阅读 0赞

# 莫队算法 #

## 0x00 简介 ##

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

## 0x01 具体思路 ##

*  那么我们如何构造这一精妙的顺序呢？
 *  我们把整个序列分成 $ \\sqrt\{n\} $ 块，每块大小就是 $ \\sqrt\{n\} $ ，然后将询问重新排序，第一关键字为左端点所在块的序号，第二关键字为右端点的坐标
 *  我们发现，对于同一个块内的询问，左端点位移一次不超过 \$\\sqrt\{n\}\$，右端点单调增，这样对于一个块内的询问，左端点移动不超过 $ t\\sqrt\{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序分块就行！终于搞完了糖果公园
 *  更新：我王室联邦写错了！！！！

转载于:https://www.cnblogs.com/LoveYayoi/p/6745518.html