莫队

莫队就是离线处理一些问题。

当一个问题[l,r]可以由[l-1,r],[l,r+1],[l+1,r],[l,r-1]相差一的区间由o(1)或o(logn)推出时，就可以用莫队莫队实质上是离线处理，通过改变询问的顺序使复杂度降到o(n^1.5)

其实莫队用到分块的地方仅仅是排序中用到？

排序的过程：先计算每个位置应该处于哪个块中,记为pos[i]，按（pos[i],r）双关键字排序，然后再对每个区间暴力计算

bzoj2038&&bzoj3781

题解太多了

大概就是个裸的莫队

bzoj2038

bzoj3781