GSS5 In this sum I can’t understand why can’t we take the minimum of x1,y1,x2,y2 as the lower limit and maximum of those as the higher limit and then find the bestsum of (lower,higher)
Can anyone explain this??
If you take the minimum and maximum of the given range to perform a query, it is then possible that the maximum sum of a segment you calculate is not in the range.
Let’s consider an example.
x1 = 1, x2 = 3, y1 = 3, y2 = 5;
According to your technique, the query performed on i = 1 to j = 5 should yield the correct answer. But as we can see that in a query from 1 to 5 the result can be such that the maximum sum is obtained in the range [4, 5]. But since x1 <= i <= y1 and x2 <= j <= y2, we can see that 4 is not in the range [x1, y1] = [1, 3]. Hence you will get an incorrect result.
Here is the hint to the solution. Consider two cases, in which (x1, y1) and (x2, y2) are overlapping and the other where they are disjoint. Can you come up with a way to combine answers on different ranges to give the optimal result?
Hint: Solve GSS1.
2 Likes
yeah i got it thanks 
Can you look into this??
http://discuss.codechef.com/questions/57254/treap-vs-avl-trees-treap-vs-red-black-trees