莫队学习笔记

莫队学习笔记

什么是莫队？

莫队是一种离线数据结构类的算法。
我们先考虑一类问题：
在一个序列上面查询区间信息。那么对于这样一类问题，首先想到各种高级的数据结构。
但莫队也可以很好的实现它。

普通莫队

莫队的思想是：如果我们已经了\([l,r]\)的区间信息，我们便可以通过指针转移暴力的快速转移到其他区间。这样，我们每一次都只需要通过前一次的区间信息得出下一次的区间。

但是有一个大问题，要是毒瘤出题人要你这个区间在最左边和最右边来回左右横跳，那就完了，时间复杂度被卡到了\(O(n^2)\)
怎么办？
莫队的精髓就在于离线操作，把所有的询问按分块的思想来调整，排序。我们可以把它们分成\(\sqrt{n}\)块来处理排序，这样子我们就可以减少区间跳动次数，来保证时间效率。