P3372 题解·新法

· · 题解

既然是线段树板子题，那肯定要不使用线段树啊！

考虑分块，正常分块单次询问是 O(\sqrt{n}) 的，虽然可以过题但不够优秀。

考虑优化这个过程。

我们可以考虑分两次块，第一层块长是 B，称其为“大块”，第二层块长是 b，称其为“小块”。

那么每次修改和询问都会被分成若干大块，若干小块和若干散点的形式。

大块的数量最多为 \frac{n}{B}，小块的数量最多为 \frac{B}{b}，散点的数量最多为 b。

单次询问是 O(\frac{n}{B}+\frac{B}{b}+b)\ge O(\sqrt[3]{\frac{n}{B}\times\frac{B}{b}\times b})=O(\sqrt[3]{n}) 的。

等号当且仅当 B=\sqrt[3]{n^2},b=\sqrt[3]{n} 时取得。

当然你也可以分更多层，但是随着层数增加，常数逐渐增大，效率也逐渐降低，同时码量的增加会让你痛不欲生。

代码及效率比较。

upd on 2024-07-18:其实我没有必要写的这么傻逼，可以直接设一个定值块，这样代码就看起来没那么傻逼了。