本文从WordPress迁移而来, 查看全部WordPress迁移文章
线段树
题意:略
已经很久没有做线段树的题目了,一道简单题目复习一下。线段树的节点应该包含什么信息是由具体问题而定的,该问题涉及到区间修改和区间求和,所以设置线段树的节点信息如下
1 | struct segment{ |
其中sum表示该区间当前的和,c表示该区间当前的增量。c其实同时肩负了两个作用,对一个区间的子区间进行了修改后,那么这个区间的增量就被破坏掉了,不是统一的,所以可以设置一个标记变量,记录该区间当前情况下增量是否统一,单增量不统一的时候,是不能传递给左右孩子区间的。但考虑我们也要记录一个区间的增量,所以干脆被增量和标记合一,单增量为0时,可能有两个意义
- 刚建完树,增量为0
- 在操作过程中增量不统一
两者意义虽然不同,但是效果是一样的,所以可以合并
因为lazy标记就派上用场了,比较简单的题目,不累述
注意会超int,用long long
1 |
|