I'll try to explain how to reach the formula. Lets solve a very easy version of the problem first i.e. suppose a box gets destroyed before the next box arrives. So whenever a box arrives, there are no other boxes on the staircase. Now, suppose you have to answer the same query for a box with width $w_{i}$. The answer for this query would simply be $a[w_{i}]\ $. Why? Since our box has width $w_{i}\ $, it spans from the complete left to the $w_{i}$'th stair, thus the answer should be the largest height between indices $1$ and $w_{i}$ (considering 1 based indexing). Also, we know that $a$ represents a staircase, increasing from left to right i.e. array $a$ is in nondecreasing order, so the stair having maximum height between indices $1$ and $w_{i}$ should be the $w_{i}$'th stair. Thus the answer in this case is simply $a[w_{i}]$. Keeping in mind the easier case, lets come back to the original problem. Now older boxes are not destroyed. Suppose the first box to fall has height $h_{1}$ and width $w_{1}$ and the second box to fall has height $h_{2}$ and width $w_{2}$. The answer for the first box will be $a[w_{1}]$ since this is similar to the easier case we discussed earlier as this is the first box. Let this answer (for the first box) be $L$ ( = $a[w_{1}]$). Now, the answer for the second box may be affected by the first box. If the first box was destroyed, the answer for the second box would be $a[w_{2}]$. But what happens if the top of the first box reaches a height greater that the height of the $w_2$'th stair. If this happens then the second box will collide with the first box before the $w_2$'th stair and remain there. So the answer for the second box = $max(height\ of\ the\ top\ of\ the\ previous\ box,\ a[w_{2}]) = max(L+h_{1},\ a[w_{2}])$. This problem could be solved without any special data structure because all the boxes always begin at the first staircase i.e. on the extreme left. You would need something like a segment tree to solve the case where the starting position of the boxes is also specified. I hope I was clear enough. Do have a look at the picture given in the problem statement for a better understanding of the cases we discussed. answered 03 Jul '18, 00:20
