P8353 [SDOI/SXOI2022] 无处存储

本文主要是介绍P8353 [SDOI/SXOI2022] 无处存储，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P8353 [SDOI/SXOI2022] 无处存储

树路径加值路径求和，强制在线。

\(n \leq 7\times 10^6\)，\(q \leq 5\times 10^4\)，时限 \(5\text{s}\)，空限 \(64\text{MB}\)。

sol

看空间限制，\(\mathcal O(n)\) 大小的数组最多只能开两个。

首先排除线段树做法，树状数组做法三个 \(\mathcal O(n)\)，也不行。

考虑分块，时空 \(\mathcal O(\sqrt n)\)。

既然用了分块，那么就要彻彻底底，排除所有 \(\mathcal O(\log n)\) 做法，考虑树分块。

随机撒点，建虚树，分类讨论跳关键点间的块链即可。

时间复杂度 \(\mathcal O(q\sqrt n)\)，空间复杂度 \(\mathcal O(2n+\sqrt n)\)。

代码不给了。

这篇关于P8353 [SDOI/SXOI2022] 无处存储的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！