rt，此题修改个数 $\mathcal{O}(n+q)$，询问个数 $\mathcal{O}(q)$。

设块长为 $B$。

事实上修改可以通过归并排序做到单次 $\mathcal{O}\left(\dfrac{q}{B}+B\right)$，查询单次复杂度为 $\mathcal{O}\left(\dfrac{q\log q}{B}+B\right)$。

显然，当 $B$ 取 $\sqrt{q\log q}$ 时，修改和查询的复杂度均为 $\mathcal{O}(\sqrt{q\log q})$，这样总时间复杂度为 $\mathcal{O}((n+q)\sqrt{q\log q})$。

但是实测跑得很慢。

但是当 $B$ 取 $\sqrt{q}$ 时，修改的复杂度是 $\mathcal{O}(\sqrt{q})$，查询的复杂度是 $\mathcal{O}(\sqrt{q}\log q)$，总时间复杂度为 $\mathcal{O}(n\sqrt{q}+q\sqrt{q}\log q)$。

结果跑得更快了。

请问这是为什么？是我算错了吗，还是有更优的块长。

如果是啥“理论和实际另当别论”，那我没啥好说的。

谢谢 qwq。