题解 P4867 【Gty的二逼妹子序列】

2018-11-28 21:33:10


博客推广

鉴于这道题的唯一一篇题解的复杂度都有问题

所以我来发一篇复杂度比较正确的题解吧

首先莫队肯定是可以搞的, 而且毒瘤的出题人只给了 $30MB$ 空间, 莫队的空间复杂度是 $O(n)$ 的, 也比较符合这一点

与以往不一样的是, 我们在移动莫队的指针时要支持维护一个区间和, 考虑到修改的次数和移动的次数不在一个数量级上, 修改的次数要比查询的次数要多得多, 所以我们考虑一个可以支持 $O(1)$ 修改, 但查询复杂度没那么优秀的数据结构

我们考虑分块!

这样就可以让修改的复杂度降到 $O(1)$ 了, 但查询是 $O(\sqrt{n})$

总复杂度为 $O(m\sqrt{n})$ 的, 相比用树状数组的复杂度 $O(m \sqrt{n} \cdot logn)$ 还是要优秀很多的