Its beautiful how a simple data structure, especially Segment Tree, can be used to solve such a variety of problems. The problem was solved using 2 segment trees built on binary arrays i.e all elements are 0 or 1 and were used to query the number of subarrays in range [l,r] consisting of only 1s. Check out the video to learn: Here is yet another application of Segment Trees in solving another mediumhard problem from Codechef NOV17 Long Challenge. Keep sharing, keep loving. asked 13 Nov '17, 21:55

One other possible approach using segment tree could to maintain 5 values in every node. Invalid (greater than R) value from right, Invalid (less than L) from right, Invalid (greater than R) value from left, Invalid (less than L) from left and answer for node. Merging can be done by taking union of all valid subarrays while merging. Link answered 14 Nov '17, 06:16

A very nice and clear explanation sir. Just awesome answered 20 Nov '17, 02:36

Your video editorial are just amazing i tried this problem for 3 days but didnt able to get the trick for 100. But finally after this video get it completely. Thanks for this video editorial.☺️
@droy0528 Thanks :)