HDOJ 4578/2013年杭州邀请赛C题 - Transformation 线段树...比较蛋疼的维护PushDown

HDOJ 4578/2013年杭州邀请赛C题 - Transformation 线段树...比较蛋疼的维护PushDown

题意:

很裸.......

题解:

因为要统计3个次方...构造三颗线段树(同时更新查询)sum[1][MAXN]为一次方...sum[2][MAXN]为二次方..sum[3][MAXN]为三次方..

首先看如何更新...令[l,r]长度为len最容易的是区间[l,r]复制相为c...sum[1][now]=len*c

sum[2][now]=len*c*c

sum[3][now]=len*c*c*c

区间[l,r]乘c也容易:  sum[1][now]=sum[1][now]*c

sum[2][now]=sum[2][now]*c*c

sum[3][now]=sum[3][now]*c*c*c

区间求和..    先sum[3][now]...因为(a+c)^3=a^3+3a^a*c+3*a*c^2+c^3.则sum[3][now]=sum[3][now]+3*sum[2][now]*c+3*c*c*sum[1][now]+c*c*c*len

再sum[2]][now]  因为(a+c)^2=a^2+2ac+c^2..则sum[2][now]=sum[2][now]+2*sum[1][now]*c+c*c *len

最后 sum[1][now]..直接sum[1][now]=sum[1][now]+len*c

这些都比较简单....关键是维护懒惰标记...有三个操作..对于每个点就有三个懒惰标记来维护...但是操作间是有顺序的..比如先做了+/*运算..后面来个赋值运算..前面的运算就不做效了..又现做乘法再做加法和先做加法再做乘法..结果是完全不同的...我的解决办法是定了一个运算顺序..推进懒惰标记时..先处理赋值运算..再处理乘法运算..最后处理加法运算..在更新懒惰标记时..也保持这种顺序运算的正确性..

Program:

#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。