莫队算法总结

写了几道莫队,总结下。
目前只会区间莫队。。树上莫队以后再补。

莫队算法学习

说说我自己的理解:
莫队算法是一类用来处理离线静态区间问题的算法。
必须是离线,而且对区间没有修改。
还要满足,如果我们知道区间[l,r]的答案,那么知道区间[l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案都是平凡的。。也就是O(1)可以实现才可以。

本质的话。。感觉就是分块+暴力? 通过离线操作,把查询按照某种顺序均分使得复杂度降低。

除了bzoj的权限题。。。区间莫队基本都A掉了。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz