# 6906. Raining Parabolas

**Problem Summery**

_{i}( 0≤i<n ), we have to perform an update operation for a given range [i,j] such that, h

_{x}= (h

_{x}+ f(x))%M, ( i≤x≤j and f(x) = ax

^{2}+bx+c ). We also have to perform a query operation for a range [i,j] such that, result = (h

_{i}+ h

_{i+1}+ h

_{i+2}+ … + h

_{j})%M.

**Solution Idea**

Solution idea with the help of a
segment tree is quite simple. First, we need to observe the types of
information we need to store on each node of the tree. As we will be facing
range updates, lazy propagation can be utilized, so, we can have three carry
variables, namely

*ca*,*cb*,*cc*. If we look closely to the update procedure, parts with x^{2}are added together and parts with x are added together and there is another part which are the constants. We can resemble them namely with variables,*a*,*b*,*c*, i.e.*a*is the variable that holds the sum for x^{2}part,*b*is the variable that holds the sum for x part and*c*is the last one that holds the constant part. Also, we can keep the pre-computed values of sum of x^{2}and x on tree node ranges for the ease of calculation.
Now, let’s dissect the update part.
Say, on node p (i to j) we already have in

*a*:
a

_{1}x_{i}^{2}+ a_{2}x_{i+1}^{2}+ a_{3}x_{i+2}^{2}+ … + a_{n}x_{j}^{2}
Now we want to add a new parabola (a,
b, c) on this range, as only x

^{2}parts will be added here, so the new value of*a*on this node will be:
(a

_{1}+a)x_{i}^{2}+ (a_{2}+a)x_{i+1}^{2}+ (a_{3}+a)x_{i+2}^{2}+ … + (a_{n}+a)x_{j}^{2}
So, we can easily see the extra value
added with the previous in variable

*a*:
a * (sum of x

^{2}in range [i,j])
Similarly, for x part, i.e.
variable

*b*we can show the added value is:
b * (sum of x in range [i,j])

And for the constant part, i.e.
variable

*c*we can show the added value is:
c * n where n is the size of range
[i,j];

So we can perform these updates now
using lazy propagation, and query is also done in the similar way, the final
result for a range is simply the sum of variable

*a*,*b*,*c*from that range. And obviously modulus operations must be handled properly.
Have fun!