JOISC 2023 Day1T1

H_Kaguya · 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，使用单调栈建虚树。

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