自动搬运

查看原文

来自洛谷，原作者为

	H_Kaguya AFO

搬运于2025-08-24 22:47:23，当前版本为作者最后更新于2023-05-27 20:38:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

单纯的追求优秀的复杂度。
如果只是想做完这道题可以忽略本文。

前置知识：整体二分。

首先，这道题的经典做法是树上主席树，时间空间都是 $O(n \log n)$。

但事实上这道题可以使用整体二分做到 $O(n \log n)$ 的时间复杂度和 $O(n)$ 的空间复杂度。

整体二分的话还是常规思路，我们去枚举一个值 $mid$，即只在 $c_i \le mid$ 的时候使用银币。
如果想要做到 $O(n \log n)$ 的复杂度，那么复杂度应该是 $T(x) = 2T(\frac{x}{2}) + O(x)$，也就是链求和的部分要做到线性。
不能使用带 $\log$ 的数据结构维护，那么就考虑树上前缀和。

我们需要保证每次只对有用的点做前缀和。
所以容易想到虚树。

具体的，我们可以把所有费用在当前二分区间内的点拿出来建虚树。
同时，对于每个树链询问，都可以差分成 $O(1)$ 个树上前缀询问。
把这些点也放到虚树上。
分治的时候把点按照费用大小递归到两边即可。

实现细节的话，首先需要把所有的点按照 DFN 序排好，分裂的时候不打乱相对顺序以避免建虚树的时候排序。
另外，需要接一个 $O(1)$ LCA，使用单调栈建虚树。

常数很大，仅分析理论复杂度就好了。