PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:Medium PREREQUISITES:segment tree, lazy propagation, basic maths PROBLEM:Given array $A$ of $N$ size and $M$ operations of type:
QUICK EXPLANATION:================ EXPLANATION:================ BASIC SEGMENT TREE STUFFI assume you know how segment trees and lazy propagation work and the basic concepts behind them like time complexity, nodes, intervals. First, I'll introduce some terminology I'm going to use.
Let's think step by step here.
Let's see how we use above two points to find here a solution using segment trees. Let's see the query part first: query is range sum, so merging two intervals is easy, just take the individual sums. THE LAZY PROPAGATION SOLUTIONNow, let's see how we can handle all updations in such a way that we can find answer for an interval without actually updating the whole interval. We are going to store some data about the updations being done at that interval node and process it to find the answer. What could be this data? How do we find out? We need to observe what kind of operations we are doing. After some certain updations, our $A_i$ could be transformed to something like $((A_i*v_1 + v_2)*v_3 + v_4 + v_5)*v_6 + v_7$, where $v_1$ to $v_7$ are values of range multiplication or range addition. Now, we can store all these values $v_1$ to $v_7$ at our node, but we might have to do $O(\textrm{number of queries})$ operations at each node, which is not really sublinear. We need to find a compact notation at each node interval. Now, thing worth noting here is that $A_i$ has been transformed to a linear function of $A_i$ i.e. something of form $(\textrm{mul}*A_i + \textrm{add})$. Now, let's say I make one more multiplication range update $v$, what's the new value of $A_i$. It's $(\textrm{mul}*v*A_i + \textrm{add}*v)$. So, we update $\textrm{mul}$ $*=$ $v$ and $\textrm{add}$ $*=$ $v$ at our node. Similarly, if we make a sum update with value $v$, the new value of $A_i$ is $(\textrm{mul}*A_i + \textrm{add} + v)$, so we update $\textrm{add}$ $+=$ $v$. For setting all elements to $v$, we can just make one multiplication with $0$ and then addition with value $v$. So, if this interval is in range $L$ to $R$, for interval sum, we need $\sum_{i=L}^{R}(\textrm{mul}*A_i + \textrm{add}$) which we can write as $(RL+1)*\textrm{add} + \textrm{mul}*\sum_{i=L}^{R}A_i$. So, we have to store sum of original $A_i$ and $R$ and $L$(basically size) and two variables $\textrm{mul}$ and $\textrm{add}$ at each node. Now, to make things easier we can just directly store the $\textrm{sum}$ of a node(i.e.* sum of all elements in that interval) instead of storing sum of original $A_i$. Then, for each range multiplication update or range addition update, we also update this $\textrm{sum}$ along with the variables $\textrm{mul}$ and $\textrm{add}$. Also, as we do we in lazy propagation, we propagate the laziness to the children of a node, if we need to query a children of a lazy node. In this problem, we can individually propagate variables $\textrm{mul}$ and $\textrm{add}$. So, if at a node $\textrm{mul} \ne 1$, then we can say that this node is multiplication lazy and if required, we'll propagate this variable down to the children of this node. Similarly, if at a node $\textrm{add} \ne 0$, we can say that this node is addition lazy and propagate this laziness down to its children. COMPLEXITY:For building the segment tree we need $O(N \textrm{log} N)$ and each query is $O(\textrm{log} N)$, so total complexity is $O(N \textrm{log} N + Q \textrm{log} N)$. PROBLEMS TO SOLVE:QSET AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 26 Jun '15, 07:54

This was an amazing problem! Took a lot of tinkering and checking. And obviously required some common sense :) answered 13 Jul '15, 15:48

+1 to the editorialist, explanation is great, and mentioning the similar problems for practice, I really appreciate his efforts and Thanks!! answered 13 Jul '15, 17:16

I think you have made a mistake in this sentence where you write
Later on you write answered 13 Jul '15, 15:45

Great problem. Really felt nice to solve this one. Thanks to the author. answered 13 Jul '15, 16:38

What it is not mentioned is how you really do the propagation,a key element in this problem. This was my biggest problem. Here the priority of operations is important. You cannot do the propagation how you want... So if you propagate from a node to right node,you know that the updates from node where made later( because of propagation itself). Let's say sum in right node is X(after we make all updates with its vals , add and mul).Now we come with information from node,knowing it was made later,it comes like that:(X+a1+a2+a3)a4a5+a6 .... So mul and add from right node become mul=mulnode and add=addmulnode+addnode That observation was important to me and I spent some time thinking .... If any of you found a easier way,please let me know! :) answered 13 Jul '15, 22:32

What's wrong with my solution? https://www.codechef.com/viewsolution/7919583 answered 14 Sep '15, 19:28

Is it possible to solve this problem using BIT and are there any other approaches for solving first 3 subtasks other than segment tree ? answered 13 Jul '15, 15:21
3
Before switching to segtree i did square root decomposition http://www.codechef.com/viewsolution/7349823 . It worked for 1st 2nd and 4th subtask but not for 3rd subtask .
(13 Jul '15, 15:52)
@rajat1603: did you try applying fast I/O to your solution? it may get AC.
(13 Jul '15, 16:04)

i did all the things specified above...buy creating an add[]and multiply[]array...and calculating the sum with lazy propagation still i was getting TLE all the time...i dont know where i was wrong....here is my code.. http://www.codechef.com/viewsolution/7474886 pls can someone tell me whats wrong...it will be a great help..
link
This answer is marked "community wiki".
answered 13 Jul '15, 16:13
I think your code is update all the elements in the range as you are using the statement  if(st!end)... i.e. you are not using lazy propagation. Lazy means to update when and only required, update it leaf nodes and return immediately. For details refer to http://www.spoj.com/forum/viewtopic.php?f=27&t=8296.... Also, Please indent your code for others to understand it easily....
(14 Jul '15, 21:04)

How (if) can we use 'heavy light decomposition' to solve this problem? answered 13 Jul '15, 16:43
