自动搬运

查看原文

来自洛谷，原作者为

	jiangxinyang2012 我常常追忆过去。

搬运于2025-08-24 22:51:44，当前版本为作者最后更新于2025-03-06 10:17:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

做这题做的人都傻了。

我们发现题目中的修改操作在线段树上其实就是一个从叶子到根的路径修改。

如图是一种将样例中 $5$ 号节点乘 $2$ 时广义线段树上修改的路径。

由于广义线段树是一棵树，所以直接在上面树链剖分就好了。

code

时间复杂度 $O(n\log^2 n)$，可以通过。