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

[博客推广](https://www.vixbob-lwc.pw) 鉴于这道题的唯一一篇题解的复杂度都有问题 所以我来发一篇复杂度比较正确的题解吧 首先莫队肯定是可以搞的， 而且毒瘤的出题人只给了 $30MB$ 空间， 莫队的空间复杂度是 $O(n)$ 的， 也比较符合这一点 与以往不一样的是， 我们在移动莫队的指针时要支持维护一个区间和， 考虑到修改的次数和移动的次数不在一个数量级上， 修改的次数要比查询的次数要多得多， 所以我们考虑一个可以支持 $O(1)$ 修改， 但查询复杂度没那么优秀的数据结构 我们考虑分块！ 这样就可以让修改的复杂度降到 $O(1)$ 了, 但查询是 $O(\sqrt{n})$ 总复杂度为 $O(m\sqrt{n})$ 的， 相比用树状数组的复杂度 $O(m \sqrt{n} \cdot logn)$ 还是要优秀很多的