介绍
莫队算法可以解决一类可离线且在得到区间 [l,r] 的答案后可在 O(1) 或 O(log2 n) 的时间复杂度内得到 [l-1,r] 和 [l,r+1] 区间内的答案的问题
浅析
对于区间 [l1,r1],[l2,r2] 从 [l1,r1] 到 [l2,r2] 的复杂度为 O(|l1-l2|+|r1-r2|),若把两个区间看成平面上的两个点,则复杂度为两点之间的曼哈顿距离
若是有 n 个区间,则可把 n 个区间看成 n 个点,所以,最小的花费就是连通这 n 个点的曼哈顿距离之和,即最小曼哈顿生成树
求曼哈顿最小生成树略麻烦,换一种方法
方法
- 把查询区间按照左端点排序
- 把查询区间按照右端点排序
- 从左到右计算区间 [l,r] 内的解
- 调整 l,r 并修改
复杂度
- 时间复杂度 O(n*sqrt(n))
- 空间复杂度视情况而定
参考
讲的不是很透彻,应该比较通俗,有不懂的可以看莫队算法