Argvchs 说我不会根号算法，把之前的博客搬过来，然后再补点东西。
一种离线算法，可以用 \(O(n\sqrt n)\) 的复杂度处理区间查询问题，当然，也可以带修，下文也会提到。
关于复杂度
莫队优化的关键是排序 + 分块，将每个询问离线下来，按照左端点所在块从小到大排序，假如左端点在同一个块，按照右端点从小到大排序。
处理问题时，我们可以通过移动左右端点来不断更新区间答案，而且排序后前后两个左端点的距离（移动次数）不会超过 \(2\times \sqrt n\) 次，总共 \(n\) 个查询，复杂度相乘也就是 \(O(n\sqrt n)\)。而因为右端点无序，但是固定左端的情况下按升序排列，所以因为左端有 \(O(\sqrt n)\) 块，而右端点一次移动 \(O(n)\) 次，总的也就是 \(O(n \sqrt n)\)。所以，莫队算法的总复杂度就是 \(O(n\sqrt n)\)。
其实，这种排序方式并不是最优解，最优解应该按照曼哈顿距离建最小生成树，但因为本身写这个就是暴力算法，这个也就无所谓了。
一种优化方式，奇偶性排序。在移动莫队指针的过程中，两个询问之间左右移动，可能会出现多余移动的情况，那么我们可以按照奇块正序，偶块反序的方式来排序，可以优化 30% 左右。
P1972 HH的项链
模板，开桶维护区间数个数,虽然加强了数据，卡卡也是能过的。
Submission
P1494 小 Z 的袜子
假设有 \(k\) 个相同的数，那么会有 \(\left (_{2}^{k} \right )\) 种选法，总共 \(\sum \left (_{2}^{cnt_x} \right )\) 种，\(cnt_i\) 表示 \(i\) 的数量。区间内随便选一对的方案数是 \(\left (_{2}^{r-l+1} \right )\)，答案就是这俩比一下就完了，之后莫队扩缩区间维护。
Submission
P5268 [SNOI2017] 一个简单的询问
记 \(get(l,r,x)\) 表示 \([l,r]\) 区间内 \(x\) 的出现次数，求 \(\sum get(l_1,r_1,i)\times get(l_2,r_2,i)\)。
会发现这个式子很难直接推，考虑做一下差分，\(get(l_1,r_1,x)\) 可以拆成 \(get(1,r_1,x) - get(1,l_1-1,x)\)。
拓展到整个式子(令 \(g(l,x)\) 表示 \(get(1,l,x)\))
做个前缀和，就可以将整个式子当作四个询问，直接莫队统计答案即可。
Submission
P4396 [AHOI2013] 作业
这题相对于板子，只是加了个取值在 \([l,r]\) 的限制，对于这个东西，完全可以考虑树状数组，每次莫队扔进树状数组，出来直接前缀和统计答案即可。
复杂度 \(O(n\sqrt n\log n)\)。
Submission
带修莫队
在区间问题中，可能会存在修改操作，虽然是离线算法，但莫队也是能做的。
假设普通莫队有 \((i,j)\) 两个维度，表示区间左右端点，那我们可以再加上一维时间维 \((i,j,t)\) 表示区间在第 \(t\) 秒的答案。
P1903 数颜色 / 维护队列
以本题为例，将时间维加入排序，当作排序的第三关键字。莫队操作中，假如当前有一个修改操作，将 \(a\) 位置与 \(b\) 位置交换，将 \(a\) 位置 \(del\)，将 \(b\) 位置 \(add\)。即可，反操作只是将 \(a\)，\(b\) 交换。
Submission
树上莫队
现在考虑将莫队放到树上，其实直接按照欧拉序把树扔到一维平面上，欧拉序这东西就是每次深搜走到走回来都记录一下，这东西剖一下就好了，但是 \(lca\) 可能不在一段欧拉序中，所以需要特判，之后做莫队即可。
Count on a tree II
模板题。
Submission
P4074 [WC2013] 糖果公园
给定树上 \(n\) 个数，每个数有 \(w_i\) 的权值，区间内第 \(i\) 个数的价值权重是 \(v_i\)，总权值定义为区间内 \(\sum w_i\times v_{cnt_i}\)，每次单点修改或者查询链上价值和。
由于是普通莫队，直接增加/减少上式即可，没什么好强调的，重点的是时间维度的意义，代表的是修改操作的下标，对应修改操作也是原树内固定的，不用再映射，注意欧拉序上的分类讨论，标记数组不要忘记。
Submission
回滚莫队
变种莫队，用于处理难以增加/删除的问题，比如区间众数，\(O(1)\) 增加,\(O(n)\) 删除，我们就可以只进行一类操作，通过回滚解决问题，这也将回滚莫队分为只增不删莫队和只删不增莫队，此处先介绍只增不删莫队。
回滚莫队的流程：
-
序列分块，划分出每个询问左右端点的所在块，通过排序使得左端点按所在块排序，右端点根据左端点升序排列。
-
分情况讨论，假如 \(l\) 和 \(r\) 在同一块内，我们可以 \(O(\sqrt n)\) 的处理询问
-
记 \(l\) 和 \(r\) 为莫队操作的区间，假如 \(l\) 和 \(r\) 不在同一块内，\(L\) 和 \(R\) 为左端点所在块的左右端点，\(x\) 和 \(y\) 为询问的左右端点。初始时，令 \(l \gets R+1\)，\(r \gets R\)。
-
介于这种情况下通常认为增加是 \(O(1)\) 的，我们先移动 \(r\) 至 \(y\)，记录下当前答案，然后新建变量，记录 \(l^{'}\) 向左增加的答案，之后统计答案，将 \(l\) 指针删掉来时增加的量，回到 \(R+1\)，实现回滚。
-
当然，这只是一个块内询问的处理方法，假如当前询问与上一次询问不在同一块内，需要重新移动 \(l\)，\(r\) 至 \(R+1\)，\(R\)，或许可以将这种回滚莫队看作对每个块都做一遍莫队（ ? ）。
AT_joisc2014_c 歴史の研究
价值定义为区间内某值出现次数与该值的乘积，每次询问求区间最大价值。
好像比板子还要板，拿这个当板子挺好。
Submission
P5906 【模板】回滚莫队&不删除莫队
定义价值为区间内相同值的下标差绝对值，求区间价值最大值。
记区间内每个值出现的最早/最晚出现的位置为 \(min_{a_i}\)，\(max_{a_i}\)，向右增加时，注意需要时刻更改 \(max_i\)，在回滚时，假如当前 \(max_i = i\)，说明已经找到了最靠右的位置，直接清零。
注意莫队的移动顺序和数组清理。
Submission
关于莫队的一些注意问题
奇偶优化回滚莫队是不能用的。
注意莫队移动指针时的顺序：
while(l>q[i].l) add(--l);
while(r<q[i].r) add(++r);
while(l<q[i].l) del(l++);
while(r>q[i].r) del(r--);