PSHTRG - Editorial

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.


very nice editorial @adkroxx


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. :slight_smile:


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. :smiley:

1 Like
@kailashnath199 Thank you Man. Now, i am able to do this question using segment tree.
Thank You.