一个优雅的暴力 –alan_cty
莫队算法的实现就是以某种规则给询问排个序然后暴力求解。
对于一个长度为$n$序列，我们给出$m$个询问，每次会询问某一段区间$[l,r]$的一些信息。
如果把区间$[l,r]$的答案转到区间$[l+1,r]$或区间$[l,r+1]$的时间复杂度为$O(1)$，显然，由第$i$ 个询问直接转到第$i+1$个询问的时间为$O(abs(li-l{i+1})+abs(ri-r{i+1}))$。
$abs(li-l{i+1})+abs(ri-r{i+1})$不就是我们熟悉的曼哈顿距离嘛，所以只要把曼哈顿距离最小生成树建起来，沿树边跑就可以以最短的时间求出所有询问的答案。
然而我并不会建曼哈顿距离最小生成树QAQ。。。。所以，以上全在扯淡。。。
但是我们可以分块。
首先，我们以$l$为第一关键字分块排序，分成$\sqrt{n}$块，也就是说第一块的$l$的值的范围为$1$到$\sqrt{n}$，第二块的$l$的值的范围为$\sqrt{n}+1$到$2\sqrt{n}$，以此类推，第$\sqrt{n}$块的$l$值的范围为$n-\sqrt{n}+1$到$n$。
分完块之后再以$r$为第二关键字排序，使得每个块里的询问的$r$都是递增的。
排完序之后就直接暴力求解。
最坏的时间复杂度为$O(n\sqrt{n})$。
证明：
在每个块中，由于$r$是递增的，所以$r$最多只会改变$n$次，而$l$最多修改$\sqrt{n}*k$次（$k$为块中询问的个数），最多有$\sqrt{n}$个块，询问一共有$n$个，所以$r$跟$l$最多修改$n\sqrt{n}$次。
在两个相邻的块中，$l$跟$r$的转移最多也是$n$次，一共要转移$\sqrt{n}$次，所以这里的修改最多也是$n\sqrt{n}$次。
总的时间复杂度还是$O(n\sqrt{n})$。