HDU 4578 – Transformation

题目链接:HDU – 4578

题意是是区间内进行三种操作,维护区间和、平方和和立方和。三种操作分别是:

  • 覆盖操作,给定区间$[l,r]$和数$c$,将区间$[l,r]$内的数字全都变成$c$
  • 区间加法,给定区间$[l,r]$和数$c$,将区间$[l,r]$内的数字全都加上$c$
  • 区间乘法,给定区间$[l,r]$和数$c$,将区间$[l,r]$内的数字全都乘以$c$

考虑用线段树维护。洛谷P3373是这个问题的简化版本,区间加法和区间乘法同时存在时,要用线段树维护区间和就要考虑运算优先级的问题。乘法的优先级大于加法,所以当发现有乘法的lazy-tag时,加法的lazy-tag就要乘上相应的值。

这一题多了两个东西,一个是区间覆盖,一个是平方和和立方和。

区间覆盖依旧考虑优先级的问题,它的优先级大于乘法和加法,所以只要遇到区间覆盖的lazy-tag,乘法标记变为1,加法标记变为0。对于平方和和立方和,乘法标记和覆盖标记是很好处理的,加法标记可以考虑:

$$(x+a)^2 = x^2 + 2ax + a^2, \quad (x+a)^3 = x^3 + 3ax^2 + 3a^2x + a^3$$

也就是说,用三个线段树维护$x$、$x^2$和$x^3$,维护立方和的线段树的更新依赖于维护和和平方和的线段树,维护平方和的线段树的更新依赖于维护和的线段树。

这一题的操作比较复杂,很容易写错,尤其需要理解线段树下放lazy-tag的过程。在更新加法标记的时候,由于上面提到的依赖关系,应当先更新立方和线段树,再更新平方和,再更新和。

 

说点什么

avatar
50
  Subscribe  
提醒