You can also simply use Max Segment Tree: Query for the largest element, remove it (by setting the value to -infinity), and repeat it K times. Afterwards you just restore the values. This is also O(K \log n) per query.
4 Likes
Wow such a different idea . Never thought of this.
1 Like
1 Like
I knew about this solution too. But for me something else was simpler, hence I decided to describe that solution. But anyway good job. 
4 Likes
Editorial just correctly explained that if there are more than 50 nos in the range l to r then as if a plus b is less than c for all (c>b>a) then c should be greater than Fibonacci nos series having elements a b c etc. So c would exceed your upper limit
The only reason I can think of -
Weak test cases (lengths of required(valid) triangle were very close to r) i.e. number of queries giving required triangle in less number of iterations >> number of queries giving required triangle in more number of iterations
Ah, yes the intended solution uses something different too. Its a cross between a segtree and a merge sort tree. Thanks for describing the intended one. 
1 Like
https://www.codechef.com/viewsolution/17834749
@kailashnath199 Thank you Man. Now, i am able to do this question using segment tree.
Thank You.