莫队小结

用了一阵莫队,真的感觉还好用

最基础的普通莫队

可以看看我的博客

块大小$O(\sqrt n)$时最优

复杂度:$O(n\sqrt n)$

带修改莫队

模仿莫队做法

也挺好理解

块大小$O(n^{\frac23})$时最优

复杂度:$O(n^{\frac53})$

分块+莫队实现在线做法

其实主要是分块

假设分成$k$块,大小为$w$

我们求出每个$[(i+\dfrac12)w,(j+\dfrac12)w]$

需要的莫队信息

查询时通过那些信息来求解

一般来说一个区间的信息是$O(n)$级别的

我们可以分成$n^{\frac13}$块,块大小$n^{\frac23}$

时间就是$O(qn^{\frac23})$,平常$n,q$大小级别一样,可以近似认为是一样的,所以可以认为时间复杂度$O(n^{\frac53})$

空间不用说,块个数$O(n^{\frac13})$,每两个都要算,就是$O(n^{\frac23})$,因为大概每个要维护$O(n)$的

所以也是$O(n^{\frac53})$

小结

莫队还是很好写得,最普通的莫队只要100+行哦

上面那句话无视掉

莫队主要是想怎么转移比较复杂

毕竟不能$O(n)$转移啊

但是总体不难

只是可能写着写着发现有信息没维护,然后代码就越来越乱