标签为 [平衡树] 的文章

HihoCoder1034毁灭者问题

题目大意 假设你拥有 n 个魔法单位,他们从左到有站在一行,编号从 1 到 n。 每个单位拥有三项属性: si: 初始法力。 mi: 最大法力上限。 ri: 每秒中法力回复速度。 现在你操纵一个毁灭者,有 m 个操作,t l r,表示时刻 t,毁灭者对所有编号从 l 到 r 的单位,使用了魔法吸收。操作按照时间顺序给出,计算毁灭者一共吸收了多少法力。 Solution 这题其实有很多做法。可以计算每此操作的答案,也可以计算每个单位的总答案。 如果能维护出每个单位i的所有操作的时间点的序列,并算出操作两两之间的时间差。那么对于时间差dt,如果$ ......

BZOJ3223 文艺平衡树

题目大意 需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间。并在最后输出整个数列。 Solution 翻转一个区间,显然是Splay的模板题。既然是模板题,题解当然很短…… 只是用了暴力Insert建树的方法,最开始是一条链,效率可能会变低。以后要尽量用build建树的方法。 代码 C++ #include<cstdio> #include<algorithm> using namespace std; int fa[1000010],son[1000010][3],rev[1000010],size[1000010]; int root,cnt; inline void pu ......