tag:blogger.com,1999:blog-3675582796619590206.post929313427740266941..comments2024-03-19T15:01:12.924+06:00Comments on I, ME AND MYSELF !!!: SPOJ RPAR : Raining ParabolasZobayer Hasanhttp://www.blogger.com/profile/10946508827987290398noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3675582796619590206.post-26954702638268056442012-12-20T21:25:30.192+06:002012-12-20T21:25:30.192+06:00Thanks for the reply ,Zobayer.I solved MULTQ3.I wa...Thanks for the reply ,Zobayer.I solved MULTQ3.I was trying out RPAR.Can you explain in more detail how you would apply lazy propagation for this problem in particular?<br />I tried out the approach which you used in horrible,but it is not working .<br /> Anonymoushttps://www.blogger.com/profile/18226044055107641922noreply@blogger.comtag:blogger.com,1999:blog-3675582796619590206.post-18675163855366679022012-12-19T20:55:09.828+06:002012-12-19T20:55:09.828+06:00you can also try MULTQ3, that one also needs lazy ...you can also try MULTQ3, that one also needs lazy propagation.Zobayer Hasanhttps://www.blogger.com/profile/10946508827987290398noreply@blogger.comtag:blogger.com,1999:blog-3675582796619590206.post-65796193973561434982012-12-19T20:33:48.124+06:002012-12-19T20:33:48.124+06:00I am not that good with either, if I can reduce th...I am not that good with either, if I can reduce the problem to cumulative sum or differences, I would go for BIT, otherwise I will always try to use segment tree. In most of the contests, if a BIT solution passes, judges always accept the segment tree solutions as well.<br />And for the lazy propagation, I am not sure whether this reply would be sufficient, this is what happens in short.<br />Say you need to add V for each element in range [X, Y], which is a combination of several nodes in a segment tree, then instead of adding V actually over the range, we just keep a variable on each node to signify that, if we go downward from that node, we need to first add the amount, then perform current operation. This is simple, right? This idea is called lazy propagation. Say, you added 5 to a range 101 to 1342. And you have a query for a range 534 to 745. So, during the update phase, we didn't actually add 5 to the ranges actually, we stored that in the largest possible nodes that comprises the range, and during the query, we only fix the values of the nodes we actually need. If you compare these with a code that you have in your hand, I think you will easily see what is happening.Zobayer Hasanhttps://www.blogger.com/profile/10946508827987290398noreply@blogger.comtag:blogger.com,1999:blog-3675582796619590206.post-41829944609116741682012-12-19T20:24:05.678+06:002012-12-19T20:24:05.678+06:00Zobayer,thanks for your reply.I have solved GSS1,G...Zobayer,thanks for your reply.I have solved GSS1,GSS3 with segment trees without using lazy propagation.I am not able to implement lazy propagation in segment trees properly.Can you help me with that?<br />And how do you decide to use BIT or Segment tree in a particular question?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3675582796619590206.post-3988989368037241252012-12-19T19:28:02.222+06:002012-12-19T19:28:02.222+06:00This post should be a sufficient explanation, if i...This post should be a sufficient explanation, if it is not, then I would recommend solving some easier ones like GSS1, GSS3 etc.Zobayer Hasanhttps://www.blogger.com/profile/10946508827987290398noreply@blogger.comtag:blogger.com,1999:blog-3675582796619590206.post-59074857535946834782012-12-19T13:14:53.742+06:002012-12-19T13:14:53.742+06:00Hasan,https://github.com/zobayer1/SPOJ/blob/master...Hasan,https://github.com/zobayer1/SPOJ/blob/master/HORRIBLE.cpp ,<br />can you explain your solution,and your lazy propagation implementation?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3675582796619590206.post-92187203427104925062012-09-17T08:39:22.125+06:002012-09-17T08:39:22.125+06:00great blog. Vai, is it possible to write a tutoria...great blog. Vai, is it possible to write a tutorial blog about this problem http://www.lightoj.com/volume_showproblem.php?problem=1411<br /><br />if you have solved it ? আহমদ ফাইয়াজhttps://www.blogger.com/profile/13247134024136987429noreply@blogger.com