[Working] 省选数据结构题目的做 Part 1
这个系列用于记录学习省选知识点的过程中做题的笔记,系列名就是这样 因为省选的知识点真的是又多又杂,题单也是又难又长,不排除同时多个题单一起开工的情况,所以如果这一部分完成了就是
[done]
的前缀,做中就是[working]
线段树
LG P2023
线段树 2 板子题,一眼秒。取模比较沙币,直接上 __int128
比较舒适。
LG P4513
这是一个经典套路题了,线段树维护区间最大子段和,对于每个 $node$ 维护:
- $lmax$:从左端点向右延伸的最大子段和
- $rmax$:从右端点向右延伸的最大子段和
- $sum$:区间和