自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:55:09，当前版本为作者最后更新于2024-04-16 21:01:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

口胡一下。感觉挺对的。

把询问搞到重链上。考虑一条重链上权值的变化，这就要考虑他的轻子树（还有他的最下端）了。

对于一个轻子树，他造成的贡献是向上运输其高度次递增的散点之后，一直运输子树中的最大值。这里我并不知道轻子树的高度和是 $O(n)$ 还是 $O(n\log n)$，姑且当做 $O(n\log n)$ 算了。

把重链和时间抽象为二维平面，考虑一个散点和不断产生的点的贡献。可以发现，一个散点一直在往右上方运动，直到碰到一个更大的值然后没了。一个不断产生的点的左边界一开始竖直上升，然后到某个时刻会被更大值不断消去，于是向右上移动，右边界同理。于是这样的点的贡献是一个平行四边形。

先考虑求出这些图形。从左往右扫描这个平面，每个时刻可能会加入一个散点，或者一个平行四边形的右边界（和散点没区别），或者一个平行四边形的左边界。对于一个左边界，需要考虑他创死了哪些点，被哪个点创死了，可以发现直接线段树二分即可。

考虑询问。首先考虑求和，可以发现一个平行四边形可以被差分为三个直角三角形，这样就可以数点了。然后考虑最值，考虑把每个平行四边形只保留其边界变成散点的样子。散点很好维护的，这玩意就是每次往右移一格或者不动。但是如果查询区间在某个平行四边形里面就寄了，要特判。

于是这题的时间复杂度就是 $O((n+q)\log^2 n)$。