普通莫队
莫队算法（mo's algorithm）一般分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。当然也有树上莫队，带修改莫队、二维莫队等等。这篇文章主要介绍的是普通莫队算法
我们考虑一个问题，给一个序列，m次询问，每次询问你区间 [l,r] 有多少种不同的颜色。 n,m\leq 100000
尽管可以用主席树做，但是我们假装不行
先考虑*力暴**，对每次询问遍历一遍 [l,r] ，这样是 O(nm) 的，
换种方式*力暴**，定义ql和qr，表示区间 [ql,qr] 内有多少颜色，再定义cnt数组， cnt_i 表示第i种颜色在区间 [ql,qr] 出现了多少次。
我们一个一个询问处理，对于询问 [l,r] ，我们挪动xl到l，xr到r
因为这个是莫队算法的基础，所以模拟一下这个过程：
我们的初始在这个状态，假设蓝色为1，红色为2，绿色为3
那么 cnt_1=3 , cnt_2=3 , cnt_3=1 ，我们把qr向右挪一下
这样多了一个绿色， cnt_3 加1
继续挪一下
多了一个红色， cnt_2 加上1
此时我们发现，我们的右指针已经和询问的右端点重合了，接下来挪左指针
少了一个蓝色， cnt_1 减去1
现在我们得出了答案为3， cnt_1=2 , cnt_2=4 , cnt_3=2
提供这部分的代码：
我们发现，每次挪动都都是 O(1) 的，每次询问我们最多要挪动n次，所以时间复杂度还是 O(nm) 。
我们有没有办法来加速呢？
这种*力暴**的耗时就耗在挪动次数上，我们要让他挪动的次数尽量少
肯定是有的，我们将询问先储存下来，再按照某种方法排序，让他减少挪动的次数，这样会变快一些
这种方法是强行离线,然后排序，所以这样的普通莫队不能资瓷修改
那么怎么排序呢？
一种解决方式是优先按照左端点排序。
这种排序的方式，保证左端点只会向右挪，但是右端点每次最坏还是可以从最前面挪到最后面，从最后面挪到最前面，这样的复杂度还是 O(nm) ，是不行的
我们的排序是要使左右端点挪动的次数尽量少，所以这里就有一种排序方法：
将序列分成
个长度为
的块，若左端点在同一个块内，则按右端点排序（以左端点所在块为第一关键字，右端点为第二关键字）
注意，莫队的挪动操作要尽量快，若不是 O(1) 的，复杂度会原地爆炸
对于n与m同阶，一般可以设块长度为
.
以下内容可以忽略，是我口胡的证明
可以证明，这样的复杂度是 O(n\
) 的，简略的提一下证明过程
我们排序之后，每个块内均摊有根号 \
个询问的l端点，显然这l个端点的右端点是有序的，最多一共会移动n次，所以对于一个块，复杂度是 O(n)
然后有根号n个块，所以总的复杂度是 O(n\
)
但对于询问特别大的情况， O(n\
) 可能会超时，需要用其他的长度，我们来分析一下什么情况下均摊复杂度最优
然而在随机情况下，发现块大小是
反而会快一些（大约是原来的0.9倍）
（如何证明我也不清楚）
还有一种卡常方法，按照奇偶性排序，我们正常的排序方式是这样的：
奇偶性排序是这样的：
这样能快是因为指针移到右边后不用再跳回左边，而跳回左边后处理下一个块又要跳回右边，这样能减少一半操作，理论上能快一倍
注意：分块时块的大小不是固定的，要根据题目具体分析，分析的过程如上面分析m极大时的复杂度
刚刚那道数颜色其实是[SDOI2009]HH的项链，然而现在裸的莫队过不去了。
然而莫队加个吸口氧卡卡常还是能过的，不开O2会TLE 2
接下来是：P2709 小B的询问（https://www.luogu.org/problemnew/show/P2709）
经典题，是裸的莫队
一句话题意：求一个区间中每个数出现次数的平方和
还是设 cnt_i 为i在当前区间出现的次数
如果 cnt_i 多了一个，那
ans+=2*cnt[x]+1
如果 cnt_i 多了一个，那
ans-=2*cnt[x]-1
没了。
带修改莫队
普通莫队是不能带修改的
我们可以强行让它可以修改，就像DP一样，可以强行加上一维时间维,表示这次操作的时间。
即把询问 [l,r] 变成 [l,r,time]
那么我们的坐标也可以在时间维上移动，即 [l,r,time] 多了一维可以移动的方向，可以变成：
-
[l-1,r,time]
-
[l+1,r,time]
-
[l,r-1,time]
-
[l,r+1,time]
-
[l,r,time-1]
-
[l,r,time+1]
这样的转移也是 O(1) 的，但是我们排序又多了一个关键字，再搞搞就行了
可以用和普通莫队类似的方法排序转移，做到
这一次我们排序的方式是以
为一块，分成了
块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。
还是来证明一下时间复杂度（默认块大小为
）：
-
左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是 O(n）
-
若左右端点所在块改变，时间一次最多会移动n个格子，时间复杂度 O(n)
-
左端点所在块一共有
中，右端点也是
种，一共
种，每种乘上移动的复杂度 O(n) ，总复杂度
树上莫队
莫队只能处理线性问题，我们要把树强行压成一维的
我们可以将树的括号序跑下来，把括号序分块，在括号序上跑莫队
具体怎么做呢？
dfs一棵树，然后如果dfs到x点，就push_back(x),dfs完x点，就直接push_back(-x)，然后我们在挪动指针的时候
-
新加入的值是x ---> add(x)
-
新加入的值是-x ---> del(x)
-
新删除的值是x ---> del(x)
-
新删除的值是-x ---> add(x)
这样的话，我们就把一棵树处理成了序列。
好像还有对树的连通块分块的方法，不过好像比较难我也不会(
例题是[WC2013]糖果公园,这题是带修改树上莫队
题意是给你一棵树,每个点有颜色,每次询问
val表示该颜色的价值
cnt表示颜色出现的次数
w表示该颜色出现i次后的价值
先把树变成序列，然后每次添加/删除一个点，这个点的对答案的的贡献是可以在 O(1) 时间内获得的，即
发现因为他会把起点的子树也扫了一遍，产生多余的贡献，怎么办呢？
因为扫的过程中起点的子树里的点肯定会被扫两次，但贡献为0
所以可以开一个vis数组，每次扫到点x，就把 vis_x 异或上1
如果 vis_x=0 ，那这个点的贡献就可以不计
所以可以用树上莫队来求
修改的话，加上一维时间维即可,变成带修改树上莫队
然后因为所包含的区间内可能没有LCA，对于没有的情况要将多余的贡献删除，然后就完事了
code：
本文发布于洛谷日报，特约作者：codesonic
原文地址：https://www.luogu.org/blog/codesonic/Mosalgorithm