莫队，作为老少皆宜区间询问之神器，其重要性不亚于吃饭时的勺子，所以我打算写一篇很多种莫队的学习笔记。
一、莫队
众所周知，应对一个区间查询问题，最暴力的方法就是直接遍历区间，这样十分不优雅，那么如何把他变得更加优雅呢？
在线的话，要应对一个不能使用线段树之类的算法优化的询问似乎不是怎么好想，于是考虑离线。
离线下来可以干什么呢？我们考虑将上一次询问直接转移到下一次，并且一开始按照区间左端点排序，这样左端点转移时只会向右，感觉优化了许多。
然而右端点依旧可能跳来跳去，通过直接排序似乎搞不到好办法，怎么办？
我们考虑牺牲一些左端点的单调移动，换取右端点有序移动，容易想到是把总区间分成几个块，左端点在同一个块中的询问按照右端点排序。
那么我们要以什么块长 B 分块呢？
首先是左端点移动，因为一个块中的左端点无序，最坏可能每次转移均为块长 B，总复杂度为 m * B。
然后是右端点移动，一个块中的有序，但是不同块之间相差可能很大，依旧考虑最坏情况：从一个块到另一个块需要 n 次转移，那么 n/B 个块总复杂度为 n^2/B。
考虑 n=m 的情况时 B 的长度，明显应为 sqrt n。
于是，我们就获得了一种 O(n sqrt n) 离线处理区间查询的算法。
当然以上基于一次转移（即端点移动一次）的时间复杂度为 O(1)。
二、带修莫队
上面的问题中只包含了区间询问，那么如果加上修改操作呢？
稍稍利用一些可持久化（？）思想，我们可以认为，每一次修改都是创建了一个新的版本，而普通的莫队则是在一个版本上跑。
是否可以将莫队跑的版本变一变呢？
现在我们要处理版本更新到相邻版本的问题，我们可以对莫队做一些小改进。
就像上面牺牲左端点为了右端点一样，现在我们需要苦一苦右端点了。
我们将左端点处于一个块的询问按照右端点处于的块排序，如果两个询问的两个端点均处于同样的块，那么再按照处于的版本排序。
按照普通莫队进行类似的分析，如果 n,m,t （t为总版本数量）均认为同阶，那么取 B = n^(2/3) 时时间复杂度最优为 n^(5/3)。
至少比暴力好不是吗，况且不要小瞧这 n^(1/3) 的时间复杂度，暴力可过不了十万。
三、回滚莫队
以上进行的讨论均建立在 O(1) 就可以处理区间的一次增加、删除的问题，那么如果删除的操作很难实现又该如何莫队呢？
既然无法删除，那么不妨进行回退。
当然此处的无法删除指的是删除后答案不好快速统计。
在普通莫队的基础上，我们进行以下操作：
-
如果我们的区间要转移到左端点在另一个块的询问，很明显此刻必定出现删除，那么我们只能清空当前贡献，从下一个询问左端点的块开始。
-
如果当前区间左端点和询问左端点同一个块，那么首先备份当前答案，然后进行普通转移，得到答案后回退到备份的答案。当然并不是要备份下整个区间，以统计区间众数为例，我们需要维护区间内每一个数的数量，那么增加时众数容易维护，而删除时并不容易，所以删除时仅删除该数出现的次数，答案直接通过回滚维护。
复杂度类似普通莫队，若认为 n,m 同阶，那么时间复杂度也为 n sqrt n。
四、莫队——二次离线
以上的所有莫队时间复杂度均在你可以 O(1) 进行转移上，那么如果不行呢？
如果继续跑普通的莫队，那么时间复杂度就要乘上一个单次移动的时间复杂度，如何优化？
这时候考虑我们一次转移对答案造成的贡献，以向右移动为例，如果说当前莫队区间 [l,r] 向右移动的贡献形如 f(a_{r+1},l,r)，且 f(a_{r+1},l,r) = f(a_{r+1},1,r) - f(a_{r+1},1,l-1)，也就是可以差分，那么我们可以将移动离线下来一起批量处理。
例如求区间逆序对的问题。
此时莫队区间向右扩展时，f(a_{r+1},l,r) 为 [l,r] 中比 a_{r+1} 大的数的个数，可以差分，考虑离线后如何处理。
f(a_{r+1},1,r) 比较好处理，树状数组预处理即可。如何处理 f(a_{r+1},1,l-1)？
首先，我们的移动次数是 n sqrt n 的，也就是说我们对一个 f(a_{r+1},1,l-1) 必须 O(1) 处理。
一个显然的方法是按照区间右端点排序，因为左端点恒为 1，所以说只需要考虑右端点向右移动，共有 O(n) 次移动。此时一个询问便是将一个值 a 放到当前维护好的 [1,l] 区间中查排名，查的次数是 n sqrt n。
于是考虑到值域分块，使用值域分块维护 [1,l] 的区间以实现 O(sqrt n) 移动区间，O(1) 查排名，这样就实现了复杂度的平衡。
于是，在 n,m 同阶的情况下，我们达到了 n sqrt n 解决区间逆序对数量问题。当然不同阶就调块长去吧。