首页 > 代码库 > 【线段树】Gym - 100507C - Zhenya moves from parents

【线段树】Gym - 100507C - Zhenya moves from parents

线段树每个结点维护两个值,分别是这个区间的 负债 和 余钱。

按时间顺序从前往后看的时候,显然负债是单调不减的。

按时间顺序从后往前看的时候,显然余钱也是单调不减的,因为之前如果有余钱,可能会增加现在的余钱,但之前的负债不会减少现在的余钱。

所以线段树的区间合并这样做:

当前区间的负债 = 左区间的负债 + max(右区间的负债 - 左区间的余钱,0);

当前区间的余钱 = 右区间的余钱 + max(左区间的余钱 - 右区间的负债,0);

最后答案就是整个区间的负债。

代码自行脑补。

【线段树】Gym - 100507C - Zhenya moves from parents