题解：P10147 [Ynoi1999] 56TP

· · 题解

口胡一下。感觉挺对的。

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

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

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

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

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

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