Hello everyone,I know that this is segment tree based question which can be done using lazy propagation.I have just started learning segment tree and I am facing lots of difficulties.I have seen some submissions but could not get anything.Can anybody help ?This is some XYZ’s submission.I have marked the lines which are making problems.I request you to please explain.If possible the hole thought process.If you are short of time atleast the commented one.Thank you all,Have a nice day
seg[] contains ans for the intervals, lazy[] contains the number of times an interval is to be flipped.
If lazy[idx] is a multiple of 2 you don’t need to flip the coins in the interval. This idea is implemented in line number 30-31 and again in line number 57-58.
seg[idx] += lazy[idx] -> this line is not used in this problem at all.
Hi, The commented line isn’t needed and is incorrect. You only need to update the count if an odd number of flips have occurred. This is the reason for the second if statement. The value lazy[idx] is the number of flips that have occurred since the last update for this range. So to update the number of heads you need to handle the whole range. The line seg[idx] = right - left + 1 - seg[idx] is just inverting the number of tails for heads.
This is just a basic implementation of lazy in segment trees. For more details refer to se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html
Even before trying this question, I suggest you to try basic question such as just adding or multiplying or changing the values in a range and querying for the sum of interval of array. One such question is http://www.spoj.com/problems/UPDATEIT/ (it can easily be solved using BIT, but just to understand lazy in segement trees, solve it using lazy only).
Hope this helps.