莫队！！！

· · 个人记录

What-什么是莫队

莫队是在解决快速询问区间元素种类和元素个数的算法。非常暴力。

对于已知区间 [l,r]，我们可以在 O(1) 的时间里快速求出 [l,r +1] 和 [l - 1,r] 的信息。而莫队，是在离线的情况下，通过移动左右端点来获取区间信息。

而莫队算法的精髓就在于排序的技巧。

莫队对于询问的排序，对于区间 [l,r], 以 l 所在块的编号为第一关键字，r 为第二关键字从小到大排序。