How to solve this question with segment trees.
https://hack.codingblocks.com/contests/c/345/311
Question link is above
MAX_QUERY - 1 problem
There are many ways to solve this problem
One way is to make a segment tree in which each node contains a multiset of elements from l to r .
And for a particular query you can just call your query function , because multiset has its own functionality so that you can get all nos which are less than k .
And the other approach is to store a sorted array in every node of segment tree . Still space complexity will O(NlogN) because every elent can occur in atmost LogN nodes .
There are other approaches too . You can check the codeforces entries on it , these are classical problems of segment trees .