How can I solve this problem? Any kind of help regarding this problem will be appreciated.
The abridged problem is:
Given a sequence of numbers. You have to perform 3 types of queries.
1 V: Add V to the end of the sequence.
2: remove an element from the end of the sequence.
3 l r: Find the K'th largest number in the range.
`
It is guaranteed that 1 <= l <= r <= the total number of elements in the current sequence.
Problem link
you can use persistence segment tree.
Thanks abhisar1414. Can you elaborate on how can it be used?
it is similar to this problem
https://www.spoj.com/problems/MKTHNUM/
You can read about this technique here.
At the example Finding the k-th smallest number in a range.
For shorter code can't we use PBDS ? , As far as I know they are mainly bound to support these operations ....
As far as I know, it can also be solved with pbds. But can't find out the way to use it. Can you share you approach?
You can use Merge Sort Tree.
Thanks. Nice tutorial.
May be there are other solutions, but there is a relatively new and less used data structure called Wavelet Tree that supports all of these operations. I don't know how easy it is to use because I haven't implemented it yet. But if you are interested you can read about it in this IOI journal.
Interesting, I have never seen updates on wavelet trees.