洛谷P3373
线段树模板题,主要对懒标的处理要求比较高。
有三种操作:
- 区间加法
- 区间乘法
- 区间求和查询
tips:我们对一个区间进行乘k操作的时候,他之前可能存在加法lazy还没pushdown,这时候,加法lazy和乘法lazy都需要乘k。因为这个lazy是为儿子节点准备的,儿子还没进行加法操作,这次的乘法肯定也会作用于前面的加法。
另外,线段树的一些基本知识点漏洞这次也暴露了出来: pushdown操作,我们知道,每个结点的懒标都是为儿子结点准备的,所以在查询/修改到x结点的时候不需要pushdown,即将查询/修改x的儿子结点的时候才需要pushdown。
AC代码:
1 | long long a[100010]; |