莫队一般分为三种
1.普通莫队
这是一种最简单的莫队
大致的思想就是离线处理每一个提问
可以把提问排序
然后用已经知道提问->后面要求的提问
把本来的数列分成sqrt(n)块(平均分)
然后就可以做了
时间复杂度(n*sqrt(n))
模板:http://www.cnblogs.com/xuanyiming/p/8439383.html
2.可修改莫队
这个莫队是在1的基础上实现的
我们再加上一个时间T
在排序和转移的时候考虑
其余和1差不多
时间复杂度:o(n^(5/3))
模板:http://www.cnblogs.com/xuanyiming/p/8439431.html
3.树上莫队
这个是最麻烦的
我们先来一个dfs
然后可以在dfs序中,没超过sqrt(n)就新分出来一个块
然后注意把剩下的分为一个块
也可以支持修改操作
时间复杂度:o(n^(5/3))
模板:http://www.cnblogs.com/xuanyiming/p/8439734.html