Its beautiful how a simple data structure, especially Segment Tree, can be used to solve such a variety of problems.

Can you count the number of subarrays that lie in range [l,r] having maximal element in range [L,R]?

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:

CSUBQ Tutorial - NOV17 Long Challenge

Here is yet another application of Segment Trees in solving another medium-hard problem from Codechef NOV17 Long Challenge.

Keep sharing, keep loving.