莫队用来离线解决区间询问问题。复杂度$O((n+m)\sqrt{n})$
其思想对所有询问的区间按照一定的顺序来回答，而不是完全按照输入顺序在线回答，从而使历史信息得到充分利用。
对$[1,n]$进行分块，每块大小为$\sqrt{n}$。对所有询问区间按照以下规则来排序：对于两个区间，如果左端点所在的块不同，则左端点所在块编号较小的区间排在前面；如果左端点在同一个块中，那么按照右端点从小到大排序。
当上一个回答的区间是$[l_1,r_1]$，此时要回答的区间是$[l_2,r_2]$时，暴力地移动左右端点，在移动的过程中进行更新或是统计。
下面来证明时间复杂度：
左端点依次分布在块中，但块内的左端点不单调。对于块内，每一次最多移动$sqrt{n}$个单位。而移动一次$O(1)$。总共移动$(m)$次。故复杂度为$O(m\sqrt{n})$
右端点相对于每一个块是单调的。因此处理一个块右端点最多移动$n$个单位。总共$\sqrt{n}$个块。因此复杂度为$O(n\sqrt{n})$
因此复杂度为$O((n+m)\sqrt{n})$
原文：https://www.cnblogs.com/qixingzhi/p/10904582.html