【日常小测】资源采集

题目大意

给定一棵$n(n \le 52501)$个点的树，初始状态下，每一结点存储的能量为$0$
树上每一个点有两个属性$v_i,l_i$分别表示这个点每单位时间产生的能量，和这个点的存储能量的上限
再给定$q(q\le52501)$个操作，每个操作有三个属性$w_i,d_i,t_i$，表示
在$t_i$的时刻，遍历在$w_i$的子树中且与$w_i$距离不超过$d_i$的点，并收集这些点的能量
一个点的能量被收集后就会清空，询问每次操作能够收集到多少能量

解题报告

先来说一说链上的情况，我们定义$last_i$为$i$号点上一次被收集的时间
我们可以把相邻的且$last_i$相同的点合并在一起，然后询问的时候用函数式线段树来回答
如果还有什么问题的话，我们可以戳这个题：市场

现在考虑树上的情况，我们先搞出DFS序，将其作为一个点的横坐标
然后我们把深度作为这个点的纵坐标，然后把这个点扔到平面上
这样单次操作就是对于一个平面上的矩形进行操作
这个是经典的$Kd-Tree$的应用，可以做到单次操作只影响到$\sqrt{n}$个结点
于是将$Kd-Tree$子树中$last_i$相同的点合在一起，打一个标记
单次操作最多增加$\sqrt n$个标记，而每一次在$Kd-Tree$上走一次就会回收一个标记
于是总的操作次数为$q\sqrt n$的
当然我们也需要用平衡树的启发式合并，或者函数式线段树来支持询问
于是总的时间复杂度为：$O(q \sqrt n \log n)$

不过众所周知，这题的暴力是$O(nq)$的
所以非递归的暴力跑得飞快，两秒的题目暴力可以卡到一秒以内
所以考完改题的时候，所有改了的人都是用的暴力……